{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Baby Names LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #hash-table #string #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #哈希表 #字符串 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trulyMostPopular"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #婴儿名字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。</p>\n",
    "\n",
    "<p>在结果列表中，选择<strong> 字典序最小 </strong>的名字作为真实名字。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>names = [\"John(15)\",\"Jon(12)\",\"Chris(13)\",\"Kris(4)\",\"Christopher(19)\"], synonyms = [\"(Jon,John)\",\"(John,Johnny)\",\"(Chris,Kris)\",\"(Chris,Christopher)\"]\n",
    "<strong>输出：</strong>[\"John(27)\",\"Chris(36)\"]</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>names.length <= 100000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [baby-names-lcci](https://leetcode.cn/problems/baby-names-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [baby-names-lcci](https://leetcode.cn/problems/baby-names-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"John(15)\",\"Jon(12)\",\"Chris(13)\",\"Kris(4)\",\"Christopher(19)\"]\\n[\"(Jon,John)\",\"(John,Johnny)\",\"(Chris,Kris)\",\"(Chris,Christopher)\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        \"\"\"\n",
    "        使用并查集来做\n",
    "        \"\"\"\n",
    "        # 提前预处理name保存为字典格式\n",
    "        counts = defaultdict(int)\n",
    "        unionSet = dict() # 并查集， key(子孙)->value(祖宗)\n",
    "        #统计频率\n",
    "        for name in names:\n",
    "            name_split = name.split('(')\n",
    "            key = name_split[0]\n",
    "            value = name_split[1][:-1]\n",
    "            counts[key] = int(value)\n",
    "        # 处理并查集\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym[1:-1].split(',')\n",
    "            while name1 in unionSet: #找到name1的祖宗\n",
    "                name1 = unionSet[name1]\n",
    "            while name2 in unionSet: #找到name2的祖宗\n",
    "                name2 = unionSet[name2]\n",
    "            if name1 != name2:#祖宗不同要合并\n",
    "                count = counts[name1]+counts[name2]\n",
    "                trueName = min(name1,name2)#选择小的那一个 小名是祖宗 \n",
    "                nikeName = name2 if trueName==name1 else name1\n",
    "                unionSet[nikeName] = trueName\n",
    "                counts.pop(nikeName)#删除\n",
    "                counts[trueName] = count #更新数据\n",
    "        return [f\"{k}({v})\" for k, v in counts.items()]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "\n",
    "        name_count = {}\n",
    "        for c in names:\n",
    "            name, cnt = c.split('(')\n",
    "            name_count[name] = int(cnt[:-1])\n",
    "\n",
    "        # 并查集 key=子孙 -> value=祖宗\n",
    "        union_map = {}\n",
    "        for s in synonyms:\n",
    "            name1, name2 = s[1:-1].split(',')\n",
    "            \n",
    "            while name1 in union_map: # 查找name1的祖宗\n",
    "                name1 = union_map[name1]\n",
    "            \n",
    "            while name2 in union_map: # 查找name2的祖宗\n",
    "                name2 = union_map[name2]\n",
    "\n",
    "            if name1 != name2: # 祖宗不同，需要合并\n",
    "                real_name = min(name1, name2)\n",
    "                nick_name = max(name1, name2)\n",
    "                union_map[nick_name] = real_name # 小名的祖宗是真名\n",
    "\n",
    "                # 更新 name_count\n",
    "                real_cnt = name_count[real_name] if real_name in name_count else 0\n",
    "                nick_cnt = name_count.pop(nick_name, 0)\n",
    "                name_count[real_name] = real_cnt + nick_cnt\n",
    "\n",
    "        res = []\n",
    "        for name, cnt in name_count.items():\n",
    "            res.append('{}({})'.format(name, cnt))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    class UnionFind:\n",
    "\n",
    "        def __init__(self):\n",
    "            self.parent = {}\n",
    "\n",
    "        def union(self, nameA: str, nameB: str) -> None:\n",
    "            parentA = self.find(nameA)\n",
    "            parentB = self.find(nameB)\n",
    "            if parentA <= parentB:\n",
    "                self.parent[parentB] = parentA\n",
    "            else:\n",
    "                self.parent[parentA] = parentB\n",
    "\n",
    "        def find(self, name) -> str:\n",
    "            if name not in self.parent:\n",
    "                self.parent[name] = name\n",
    "                return name\n",
    "\n",
    "            ans = name\n",
    "            while self.parent[ans] != ans:\n",
    "                ans = self.find(self.parent[ans])\n",
    "            self.parent[name] = ans\n",
    "            return ans\n",
    "\n",
    "        \n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        uf = self.UnionFind()\n",
    "        for nametag in synonyms:\n",
    "            pair = nametag.split(',')\n",
    "            nameA, nameB = pair[0][1:], pair[1][:len(pair[1]) - 1]\n",
    "            uf.union(nameA, nameB)\n",
    "        ansDict = defaultdict(int)\n",
    "        for nametag in names:\n",
    "            pair = nametag.split('(')\n",
    "            name = pair[0]\n",
    "            freq = int(pair[1][:len(pair[1]) - 1])\n",
    "            ansDict[uf.find(name)] += freq\n",
    "        ans = []\n",
    "        for name in ansDict:\n",
    "            ans.append(f'{name}({ansDict[name]})')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        p, d, q = {}, {}, collections.defaultdict(int)\n",
    "        for s in synonyms:\n",
    "            a, b = s[1: -1].split(',')\n",
    "            pa, pb = p.setdefault(a, [a]), p.setdefault(b, [b])\n",
    "            if pa is not pb:    #并查集基操，对数组引用进行合并\n",
    "                pa.extend(pb)\n",
    "                for c in pb:\n",
    "                    p[c] = pa\n",
    "        for name in p:\n",
    "            d.setdefault(id(p[name]), min(p[name])) #取字典序最小名\n",
    "        for s in names:\n",
    "            i = s.find('(')\n",
    "            name, count = s[: i], int(s[i + 1: -1])\n",
    "            q[name in p and d[id(p[name])] or name] += count    #未合并过的name单独计数\n",
    "        return [f'{name}({count})' for name, count in q.items()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, names):\n",
    "        self.parent = {}\n",
    "        for name in names:\n",
    "            self.parent[name] = name \n",
    "    \n",
    "    def union(self, a, b):\n",
    "        for node in [a, b]:\n",
    "            if node not in self.parent:\n",
    "                self.parent[node] = node \n",
    "        \n",
    "        roota = self.find_root(a)\n",
    "        rootb = self.find_root(b)\n",
    "        if roota < rootb:\n",
    "            self.parent[rootb] = roota \n",
    "        else:\n",
    "            self.parent[roota] = rootb\n",
    "\n",
    "    def find_root(self, a):\n",
    "        while a != self.parent[a]:\n",
    "            self.parent[a] = self.parent[self.parent[a]]\n",
    "            a = self.parent[a]\n",
    "        return a \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        freq_map = {}\n",
    "        for name in names:\n",
    "            true_name = name.split('(')[0]\n",
    "            counter = int(name.split('(')[1].strip(')'))\n",
    "            freq_map[true_name] = counter \n",
    "        \n",
    "        dsu = DSU(freq_map.keys())\n",
    "\n",
    "        for syno in synonyms:\n",
    "            a, b = syno.strip('()').split(',')\n",
    "            dsu.union(a, b)\n",
    "\n",
    "        res_map = {}\n",
    "        for name in freq_map.keys():\n",
    "            true_name = dsu.find_root(name)\n",
    "            res_map[true_name] = res_map.get(true_name, 0) + freq_map.get(name)\n",
    "\n",
    "        return ['{}({})'.format(n, f) for n, f in res_map.items()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, names):\n",
    "        self.parent = {}\n",
    "        for name in names:\n",
    "            self.parent[name] = name  # 初始状态自己的祖先是自身，即所有 name 单独成集合\n",
    "    \n",
    "    def union(self, a, b):\n",
    "        for node in [a, b]:  \n",
    "            if node not in self.parent:\n",
    "                self.parent[node] = node \n",
    "        \n",
    "        roota = self.find_root(a)\n",
    "        rootb = self.find_root(b)\n",
    "        if roota < rootb:  # 比较字典序，字典序小的作为新的祖先\n",
    "            self.parent[rootb] = roota  # 把字典序大的合并到新的祖先\n",
    "        else:\n",
    "            self.parent[roota] = rootb\n",
    "    \n",
    "    def find_root(self, node):\n",
    "        while node != self.parent[node]:  # 直到找到最上层的根节点\n",
    "            self.parent[node] = self.parent[self.parent[node]]\n",
    "            node = self.parent[node]\n",
    "        return node \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        freq_map = {}\n",
    "        for name in names:\n",
    "            true_name = name.split('(')[0]\n",
    "            freq = int(name.split('(')[1].replace(')', ''))\n",
    "            freq_map[true_name] = freq_map.get(true_name, 0) + freq \n",
    "        \n",
    "        dsu = DSU(freq_map.keys())\n",
    "        for syno in synonyms:\n",
    "            a, b = syno.strip('()').split(',')\n",
    "            dsu.union(a, b)\n",
    "\n",
    "        res = {}\n",
    "        for n, f in freq_map.items():\n",
    "            true_name = dsu.find_root(n)\n",
    "            res[true_name] = res.get(true_name, 0) + f \n",
    "        \n",
    "        return ['{}({})'.format(n, f) for n, f in res.items()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, names):\n",
    "        self.root = {}\n",
    "        self.count = {}\n",
    "\n",
    "        for name_times in names:\n",
    "            name, times = name_times.split('(')\n",
    "            self.root[name] = name\n",
    "            times = times.replace(')', '')\n",
    "            self.count[name] = int(times)\n",
    "\n",
    "    def find(self, x):\n",
    "        root = self.root.get(x, x)\n",
    "        if x == root:\n",
    "            return x\n",
    "        else:  \n",
    "            self.root[x] = self.find(root)\n",
    "        return self.root[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x_root = self.find(x) \n",
    "        y_root = self.find(y)\n",
    "        \n",
    "        if x_root < y_root:\n",
    "                self.root[y_root] = x_root\n",
    "                self.count[x_root] += self.count.get(y_root, 0)\n",
    "              \n",
    "        elif x_root > y_root:\n",
    "            self.root[x_root] = y_root \n",
    "            self.count[y_root] += self.count.get(x_root, 0)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        uf = UF(names)\n",
    "        print(uf.root)\n",
    "        for s in synonyms:\n",
    "            x, y = s.split(',')\n",
    "            x = x.replace('(', '')\n",
    "            y = y.replace(')', '')\n",
    "            print(x, y)\n",
    "            uf.union(x, y)\n",
    "\n",
    "        ans = []\n",
    "        for name, times in uf.count.items():\n",
    "            if uf.find(name) == name:\n",
    "                ans.append('{}({})'.format(name,times))\n",
    "        return ans \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        p = {}\n",
    "        s = {}\n",
    "        \n",
    "        def find(x):\n",
    "            p.setdefault(x, x)\n",
    "            s.setdefault(x, 0)\n",
    "            while x != p[x]:\n",
    "                p[x] = p[p[x]]\n",
    "                x = p[x]\n",
    "            return x\n",
    "        \n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                p[ry] = p[rx]\n",
    "                s[rx] += s[ry]\n",
    "\n",
    "        for name in names:\n",
    "            x, c = name.split('(')\n",
    "            p[x] = x\n",
    "            s[x] = int(c[:-1])\n",
    "        \n",
    "        for x in synonyms:\n",
    "            a, b = x[1:-1].split(',')\n",
    "            union(a, b)\n",
    "        \n",
    "        print(p)\n",
    "        print(s)\n",
    "        name = {}\n",
    "        for x in p:\n",
    "            y = find(x)\n",
    "            if y not in name:\n",
    "                name[y] = x\n",
    "            else:\n",
    "                name[y] = min(name[y], x)\n",
    "        ans = set()\n",
    "        for k in name:\n",
    "            ans.add(f\"{name[k]}({s[p[k]]})\")\n",
    "        \n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        class Name:\n",
    "            def __init__(self, name:str, freq:int):\n",
    "                self.name = name\n",
    "                self.freq = freq\n",
    "            \n",
    "            def __str__(self):\n",
    "                return f\"{self.name}({self.freq})\"\n",
    "        class UnionFind:\n",
    "            def __init__(self, names):\n",
    "                self.parents = {}\n",
    "                for name in names:\n",
    "                    self.parents[name] = name\n",
    "            \n",
    "            def find(self, name):\n",
    "                if name != self.parents[name]:\n",
    "                    self.parents[name] = self.find(self.parents[name])\n",
    "                return self.parents[name]\n",
    "\n",
    "\n",
    "            def unoin(self, x, y):\n",
    "                rootx = self.find(x)\n",
    "                rooty = self.find(y)\n",
    "                if rootx == rooty:\n",
    "                    return\n",
    "                \n",
    "                if rootx.name < rooty.name:\n",
    "                    self.parents[rooty] = rootx\n",
    "                    rootx.freq += rooty.freq\n",
    "                else:\n",
    "                    self.parents[rootx] = rooty\n",
    "                    rooty.freq += rootx.freq\n",
    "\n",
    "        nameinstances = {}\n",
    "        for name_freq in names:\n",
    "            name_string, freq = name_freq.split('(')\n",
    "            freq = int(freq[:-1])\n",
    "            name = Name(name_string, freq)\n",
    "            nameinstances[name_string] = name\n",
    "\n",
    "        for synonym in synonyms:\n",
    "            name1_str, name2_str = synonym.split(',')\n",
    "            name1_str = name1_str[1:].strip()\n",
    "            name2_str = name2_str[:-1].strip()\n",
    "            if name1_str not in nameinstances:\n",
    "                nameinstances[name1_str] = Name(name1_str, 0)\n",
    "            if name2_str not in nameinstances:\n",
    "                nameinstances[name2_str] = Name(name2_str, 0)\n",
    "        \n",
    "        uf = UnionFind(list(nameinstances.values()))\n",
    "\n",
    "        for synonym in synonyms:\n",
    "            name1_str, name2_str = synonym.split(',')\n",
    "            name1_str = name1_str[1:].strip()\n",
    "            name2_str = name2_str[:-1].strip()\n",
    "            name1 = nameinstances[name1_str]\n",
    "            name2 = nameinstances[name2_str]\n",
    "            uf.unoin(name1, name2)\n",
    "        \n",
    "        answers = set([uf.find(name) for name in uf.parents])\n",
    "        return [str(name) for name in answers]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        mem = collections.defaultdict(list)\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym[1: -1].split(\",\")\n",
    "            mem[name1].append(name2)\n",
    "            mem[name2].append(name1)\n",
    "\n",
    "        #print(mem)\n",
    "        def combine_synonym(name, current_list, visited):\n",
    "            queue = [name]\n",
    "            next_queue = []\n",
    "\n",
    "            while queue:\n",
    "                for name in queue:\n",
    "                    if name in visited:\n",
    "                        continue\n",
    "                    current_list.append(name)\n",
    "                    visited.add(name)\n",
    "                    for synony in mem[name]:\n",
    "                        next_queue.append(synony)\n",
    "                queue = next_queue\n",
    "                next_queue = []\n",
    "\n",
    "        names_map = {}\n",
    "        for name in mem:\n",
    "            if name in names_map:\n",
    "                continue\n",
    "            found_names = []\n",
    "            combine_synonym(name, found_names, set())\n",
    "            first_name = min(found_names)\n",
    "            for found_name in found_names:\n",
    "                names_map[found_name] = first_name\n",
    "\n",
    "        #print(names_map)\n",
    "        \n",
    "        counter = collections.defaultdict(int)\n",
    "        for name_str in names:\n",
    "            name, freq = name_str.split(\"(\")[0], int(name_str.split(\"(\")[1][:-1])\n",
    "            if name in names_map:\n",
    "                counter[names_map[name]] += freq\n",
    "            else:\n",
    "                counter[name] += freq\n",
    "\n",
    "        ret = []\n",
    "        for name, freq in counter.items():\n",
    "            ret.append(name + \"(\" + str(freq) + \")\")\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        n = []\n",
    "        se = set()\n",
    "        for s in names:\n",
    "            ind = s.index('(')\n",
    "            n.append([s[:ind], int(s[ind + 1: len(s) - 1])])\n",
    "            se.add(s[:ind])\n",
    "        \n",
    "        for s in synonyms:\n",
    "            ind = s.index(',')\n",
    "            s1, s2 = s[1:ind], s[ind + 1: len(s) - 1]\n",
    "            if s1 not in se:\n",
    "                se.add(s1)\n",
    "                n.append([s1, 0])\n",
    "            if s2 not in se:\n",
    "                se.add(s2)\n",
    "                n.append([s2, 0])\n",
    "            \n",
    "        \n",
    "        n.sort(key=lambda x: (x[0], x[1]))\n",
    "        \n",
    "        m = {l[0]: ind for ind, l in enumerate(n)}\n",
    "        fm = {ind: l[0] for ind, l in enumerate(n)}\n",
    "        name = [i for i in range(len(n))]\n",
    "        nums = [l[1] for l in n]\n",
    "\n",
    "        def find(i):\n",
    "            while i != name[i]:\n",
    "                i = name[i]\n",
    "            return i\n",
    "\n",
    "        def unior(s1, s2):\n",
    "            i1, i2 = m.get(s1), m.get(s2)\n",
    "            if i1 is None or i2 is None:\n",
    "                return\n",
    "            f1, f2 = find(i1), find(i2)\n",
    "            f1, f2 = min(f1, f2), max(f1, f2)\n",
    "            if f1 != f2:\n",
    "                name[f2] = f1\n",
    "                nums[f1] += nums[f2]\n",
    "        \n",
    "        for s in synonyms:\n",
    "            ind = s.index(',')\n",
    "            s1, s2 = s[1:ind], s[ind + 1: len(s) - 1]\n",
    "            unior(s1, s2)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(len(name)):\n",
    "            if find(i) == i and nums[i] > 0:\n",
    "                _name = fm[i]\n",
    "                ans.append(f'{_name}({nums[i]})')\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        \"\"\"\n",
    "        将名字视为一个结点 表达同一个意思就用边连接 显然一个连通子图就对应一个名字\n",
    "        然后广度或者深度优先遍历即可\n",
    "        \"\"\"\n",
    "        # 提前预处理name保存为字典格式\n",
    "        counts = defaultdict(int)\n",
    "        for name in names:\n",
    "            idx1, idx2 = name.find('('), name.find(')')\n",
    "            key = name[:idx1]\n",
    "            value = name[idx1 + 1:idx2]\n",
    "            counts[key] += int(value)\n",
    "        graph = defaultdict(list)  # graph key是名字value是列表 列表就是邻居\n",
    "        for synonym in synonyms:\n",
    "            u, v = synonym[1:-1].split(',')\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        for name in counts.keys():#这一步主要是为了让孤岛结点加入 \n",
    "            if name not in graph:\n",
    "                graph[name] = list()\n",
    "        rs = []\n",
    "        used = set(graph.keys())  # 未访问列表\n",
    "        queue = collections.deque()\n",
    "        while len(used) > 0:\n",
    "            queue.append(used.pop())\n",
    "            num = 0  # 统计次数\n",
    "            tmp_name = None\n",
    "            while len(queue) > 0:\n",
    "                node = queue.popleft()\n",
    "                if tmp_name is None or node < tmp_name:\n",
    "                    tmp_name = node\n",
    "                num += counts[node]\n",
    "                for neiborhood in graph[node]:\n",
    "                    if neiborhood in used:  # 还没有被访问\n",
    "                        queue.append(neiborhood)\n",
    "                        used.remove(neiborhood)\n",
    "            rs.append(f\"{tmp_name}({num})\")\n",
    "        return rs\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        name_freq = dict()\n",
    "        for name in names:\n",
    "            real_name = name[:name.find('(')]\n",
    "            freq = name[name.find('(')+1: name.find(')')]\n",
    "            name_freq[real_name] = freq\n",
    "        syn_set= set()\n",
    "        syn_pair = []\n",
    "        for syn in synonyms:\n",
    "            real_syn = syn[syn.find('(')+1: syn.find(')')]\n",
    "            first = real_syn.split(',')[0]\n",
    "            second = real_syn.split(',')[1]\n",
    "            syn_set.add(first)\n",
    "            syn_set.add(second)\n",
    "            syn_pair.append((first, second))\n",
    "        self.parent = self.unionFind_init(syn_set)\n",
    "        for pair in syn_pair:\n",
    "            self.union(pair[0], pair[1])\n",
    "        \n",
    "        res = dict()\n",
    "        for name in name_freq:\n",
    "            if name in self.parent:\n",
    "                short_name = self.findParent(name)\n",
    "            else:\n",
    "                short_name = name\n",
    "            res[short_name] = res.get(short_name, 0) + int(name_freq[name])\n",
    "        return [name+'('+str(freq)+')' for name,freq in res.items()]\n",
    "\n",
    "\n",
    "\n",
    "    def unionFind_init(self, name_freq):\n",
    "        parent = dict()\n",
    "        for name in name_freq:\n",
    "            parent[name] = name\n",
    "        return parent\n",
    "\n",
    "    def findParent(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.findParent(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, p, q):\n",
    "        root_p = self.findParent(p)\n",
    "        root_q = self.findParent(q)\n",
    "        if root_p == root_q:\n",
    "            return\n",
    "        if root_p < root_q:\n",
    "            self.parent[root_q] = root_p\n",
    "        else:\n",
    "            self.parent[root_p] = root_q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        n = len(names)\n",
    "        id_name, id_freq = [], []\n",
    "        name_id = {}\n",
    "        for i in range(len(names)):\n",
    "            j = 0\n",
    "            while names[i][j] != \"(\":\n",
    "                j += 1\n",
    "            name = names[i][:j]\n",
    "            id_name.append(name)\n",
    "            id_freq.append(int(names[i][j + 1 : -1]))\n",
    "            name_id[name] = i\n",
    "        g = [set() for _ in range(n)]\n",
    "        for s in synonyms:\n",
    "            segs = s.split(\",\")\n",
    "            name1 = segs[0][1:]\n",
    "            name2 = segs[1][:-1]\n",
    "            if name1 == name2:\n",
    "                continue\n",
    "            if name1 not in name_id:\n",
    "                name_id[name1] = n\n",
    "                g.append(set())\n",
    "                id_name.append(name1)\n",
    "                id_freq.append(0)\n",
    "                n += 1\n",
    "            if name2 not in name_id:\n",
    "                name_id[name2] = n\n",
    "                g.append(set())\n",
    "                id_name.append(name2)\n",
    "                id_freq.append(0)\n",
    "                n += 1\n",
    "            id1, id2 = name_id[name1], name_id[name2]\n",
    "            g[id1].add(id2)\n",
    "            g[id2].add(id1)\n",
    "        visited = [False] * n\n",
    "        real_names = []\n",
    "        for i in range(n):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            name = id_name[i]\n",
    "            q, head = [i], -1\n",
    "            visited[i] = True\n",
    "            total_freq = id_freq[i]\n",
    "            min_name = name\n",
    "            while head + 1 < len(q):\n",
    "                head += 1\n",
    "                u = q[head]\n",
    "                for v in g[u]:\n",
    "                    if not visited[v]:\n",
    "                        visited[v] = True\n",
    "                        q.append(v)\n",
    "                        total_freq += id_freq[v]\n",
    "                        min_name = min(min_name, id_name[v])\n",
    "            real_names.append(f\"{min_name}({total_freq})\")\n",
    "        return real_names"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 面试题 17.07. 婴儿名字\n",
    "# 使用标准并查集，把字符串都转化为数字，这样好复用标准并查集代码\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        px, py = self.find(x), self.find(y)\n",
    "        if px == py:\n",
    "            return\n",
    "        if self.rank[px] < self.rank[py]:\n",
    "            self.parent[px] = py\n",
    "        elif self.rank[px] > self.rank[py]:\n",
    "            self.parent[py] = px\n",
    "        else:\n",
    "            self.parent[py] = px\n",
    "            self.rank[px] += 1\n",
    "\n",
    "    def to_ancerstor(self, i):\n",
    "        j = self.parent[i]\n",
    "        if i == j:\n",
    "            return i\n",
    "        k = self.to_ancerstor(j)\n",
    "        self.parent[i] = k\n",
    "        return k\n",
    "\n",
    "    def all_to_ancestor(self):  # make all parent to ancestor\n",
    "        for i in range(len(self.parent)):\n",
    "            self.to_ancerstor(i)\n",
    "\n",
    "    def regular(self):  # ensure the parent is the smallest one.\n",
    "        d = {}\n",
    "        for i, x in enumerate(self.parent):\n",
    "            if x in d:\n",
    "                self.parent[i] = d[x]\n",
    "            elif i < x:\n",
    "                d[x] = i\n",
    "                self.parent[i] = i\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        # 1. 把字符串都转化为数字，这样好复用标准并查集代码\n",
    "        word_set = set()\n",
    "        word_pairs = []\n",
    "        name_count = {}\n",
    "        for s in names:\n",
    "            p = s.find('(')\n",
    "            a = s[:p]\n",
    "            b = s[p + 1: -1]\n",
    "            name_count[a] = int(b)\n",
    "            word_set.add(a)\n",
    "        for ab in synonyms:\n",
    "            ab = ab[1:-1]\n",
    "            a, b = ab.split(',')\n",
    "            word_pairs.append((a, b))\n",
    "            word_set.add(a)\n",
    "            word_set.add(b)\n",
    "        word_lst = sorted(list(word_set))\n",
    "        word_dict = dict([(w, i) for i, w in enumerate(word_lst)])\n",
    "        pairs = [(word_dict[a], word_dict[b]) for a, b in word_pairs]\n",
    "        idx_count = dict([(word_dict[k], v) for k, v in name_count.items()])\n",
    "        # 2. 建立标准并查集\n",
    "        uf = UnionFind(len(word_lst))\n",
    "        for a, b in pairs:\n",
    "            uf.union(a, b)\n",
    "        uf.all_to_ancestor()\n",
    "        uf.regular()\n",
    "        # 3. 使用并查集，合并计数\n",
    "        idx_counter = Counter()\n",
    "        for k, v in idx_count.items():\n",
    "            parent = uf.parent[k]\n",
    "            idx_counter[parent] += v\n",
    "        aa = idx_counter.most_common(1)[0]\n",
    "        ans = [word_lst[k] + '(' + str(v) + ')' for k, v in idx_counter.items()]\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 204 ms ... 61 % ... 23.2 MB ... 34 %\n",
    "        #  time: O(n+m)\n",
    "        # space: O(n+m)\n",
    "        \n",
    "        def find(u):\n",
    "            if root[u] != u:\n",
    "                root[u] = find(root[u])\n",
    "            return root[u]\n",
    "        \n",
    "        def union(u, v):\n",
    "            ur, vr = find(u), find(v)\n",
    "            if ur != vr:\n",
    "                root[ur] = vr\n",
    "        \n",
    "        n = len(names)\n",
    "        loc = {s.split('(')[0]: i for i,s in enumerate(names)}\n",
    "        root = [i for i in range(n)]\n",
    "        for pair in synonyms:\n",
    "            name1, name2 = pair[1:-1].split(',')\n",
    "            if name1 not in loc:\n",
    "                root.append(n)\n",
    "                loc[name1] = n\n",
    "                n += 1\n",
    "            if name2 not in loc:\n",
    "                root.append(n)\n",
    "                loc[name2] = n\n",
    "                n += 1\n",
    "            union(loc[name1], loc[name2])\n",
    "        \n",
    "        res = {}\n",
    "        for i, s in enumerate(names):\n",
    "            name, freq = s[:-1].split('(')\n",
    "            r = find(i)\n",
    "            if r not in res:\n",
    "                res[r] = [name, int(freq)]\n",
    "            else:\n",
    "                if res[r][0] > name:\n",
    "                    res[r][0] = name\n",
    "                res[r][1] += int(freq)\n",
    "        return [name + '({})'.format(freq) for name, freq in res.values()]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        #  time: O(n+m)\n",
    "        # space: O(n)\n",
    "        \n",
    "        def find(u):\n",
    "            if root[u] != u:\n",
    "                root[u] = find(root[u])\n",
    "            return root[u]\n",
    "        \n",
    "        def union(u, v):\n",
    "            ur, vr = find(u), find(v)\n",
    "            if ur != vr:\n",
    "                root[ur] = vr\n",
    "        \n",
    "        n = len(names)\n",
    "        loc = {s.split('(')[0]: i for i,s in enumerate(names)}\n",
    "        root = [i for i in range(n)]\n",
    "        for pair in synonyms:\n",
    "            name1, name2 = pair[1:-1].split(',')\n",
    "            if name1 not in loc:\n",
    "                root.append(n)\n",
    "                loc[name1] = n\n",
    "                n += 1\n",
    "            if name2 not in loc:\n",
    "                root.append(n)\n",
    "                loc[name2] = n\n",
    "                n += 1\n",
    "            union(loc[name1], loc[name2])\n",
    "        \n",
    "        res = {}\n",
    "        for i, s in enumerate(names):\n",
    "            name, freq = s[:-1].split('(')\n",
    "            r = find(i)\n",
    "            if r not in res:\n",
    "                res[r] = [name, int(freq)]\n",
    "            else:\n",
    "                if res[r][0] > name:\n",
    "                    res[r][0] = name\n",
    "                res[r][1] += int(freq)\n",
    "        return [name + '({})'.format(freq) for name, freq in res.values()]\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        for i in range(len(synonyms)):\n",
    "            cur=synonyms[i]\n",
    "            cur=cur.split(\",\")\n",
    "            cur[0]=cur[0][1:]\n",
    "            cur[1]=cur[1][:-1]\n",
    "            synonyms[i]=cur\n",
    "        name=defaultdict(int)\n",
    "        for i in range(len(names)):\n",
    "            string=names[i]\n",
    "            cur_name,cnt=\"\",0\n",
    "            for ch in string:\n",
    "                if ch.isalpha():\n",
    "                    cur_name+=ch\n",
    "                elif ch.isdigit():\n",
    "                    cnt=cnt*10+int(ch)\n",
    "                elif ch==\")\":\n",
    "                    name[cur_name]=cnt\n",
    "                    names[i]=cur_name\n",
    "        Names=[]\n",
    "        for li in synonyms:\n",
    "            Names.extend(li)\n",
    "        Names.extend(names)\n",
    "        Names=list(set(Names))\n",
    "        ind={word:i for i,word in enumerate(Names)}\n",
    "        n=len(Names)\n",
    "        kkk=setUnion(n)\n",
    "        ans=defaultdict(int)\n",
    "        for a,b in synonyms:\n",
    "            kkk.union(ind[a],ind[b])\n",
    "        part=kkk.get_partset()\n",
    "        for p in part:\n",
    "            min_num=p\n",
    "            for idx in part[p]:\n",
    "                if Names[idx] in name and Names[idx]<Names[min_num]:\n",
    "                    min_num=idx\n",
    "            for idx in part[p]:\n",
    "                kkk.parent[idx]=min_num\n",
    "        res=[]\n",
    "        for i in range(len(names)):\n",
    "            ans[Names[kkk.find(ind[names[i]])]]+=name[names[i]]\n",
    "        for key in ans:\n",
    "            res.append(key+\"(\"+str(ans[key])+\")\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "'''\n",
    "--- 从此处复制 ---\n",
    "'''\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n=None):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "        if n: self.parent = list(range(n))\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y: self.parent[x] = y\n",
    "    def get_group_count(self):\n",
    "        return len(set(self.find(x) for x in self.parent))\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        uf = UnionFind()\n",
    "        for x in synonyms: \n",
    "            x, y = x[1:-1].split(\",\")\n",
    "            uf.merge(x, y)\n",
    "        cnts = Counter()\n",
    "        g = defaultdict(set)\n",
    "        for x in names:\n",
    "            p = x.find(\"(\")\n",
    "            x, y = x[:p], int(x[p+1:-1])\n",
    "            g[uf.find(x)].add(x)\n",
    "            cnts[uf.find(x)] += y\n",
    "        ans = []\n",
    "        d = {}\n",
    "        for k, v in g.items():\n",
    "            d[k] = min(v)\n",
    "        for k, v in cnts.items():\n",
    "            t = \"{}({})\".format(d[k], v)\n",
    "            ans.append(t)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        for i in range(len(synonyms)):\n",
    "            cur=synonyms[i]\n",
    "            cur=cur.split(\",\")\n",
    "            cur[0]=cur[0][1:]\n",
    "            cur[1]=cur[1][:-1]\n",
    "            synonyms[i]=cur\n",
    "        name=defaultdict(int)\n",
    "        for i in range(len(names)):\n",
    "            string=names[i]\n",
    "            cur_name,cnt=\"\",0\n",
    "            for ch in string:\n",
    "                if ch.isalpha():\n",
    "                    cur_name+=ch\n",
    "                elif ch.isdigit():\n",
    "                    cnt=cnt*10+int(ch)\n",
    "                elif ch==\")\":\n",
    "                    name[cur_name]=cnt\n",
    "                    names[i]=cur_name\n",
    "        Names=[]\n",
    "        for li in synonyms:\n",
    "            Names.extend(li)\n",
    "        Names.extend(names)\n",
    "        Names=list(set(Names))\n",
    "        ind={word:i for i,word in enumerate(Names)}\n",
    "        n=len(Names)\n",
    "        kkk=setUnion(n)\n",
    "        ans=defaultdict(int)\n",
    "        for a,b in synonyms:\n",
    "            kkk.union(ind[a],ind[b])\n",
    "        part=kkk.get_partset()\n",
    "        for p in part:\n",
    "            min_num=p\n",
    "            for idx in part[p]:\n",
    "                if Names[idx] in name and Names[idx]<Names[min_num]:\n",
    "                    min_num=idx\n",
    "            for idx in part[p]:\n",
    "                kkk.parent[idx]=min_num\n",
    "        res=[]\n",
    "        for i in range(len(names)):\n",
    "            ans[Names[kkk.find(ind[names[i]])]]+=name[names[i]]\n",
    "        for key in ans:\n",
    "            res.append(key+\"(\"+str(ans[key])+\")\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        union_set = dict()\n",
    "        vals = dict()\n",
    "        for name_info in names:\n",
    "            name, val = name_info.replace(\")\", \"\").split(\"(\")\n",
    "            vals[name] = int(val)\n",
    "\n",
    "        def find(name):\n",
    "            if name not in union_set:\n",
    "                union_set[name] = name\n",
    "            if union_set[name] == name:\n",
    "                return name\n",
    "            else:\n",
    "                union_set[name] = find(union_set[name])\n",
    "                return union_set[name]\n",
    "\n",
    "        def union(name_a, name_b):\n",
    "            name_a, name_b = find(name_a), find(name_b)\n",
    "            if name_a < name_b:\n",
    "                union_set[name_b] = name_a\n",
    "            else:\n",
    "                union_set[name_a] = name_b\n",
    "\n",
    "        for synonym in synonyms:\n",
    "            name_a, name_b = synonym[1:-1].split(\",\")\n",
    "            union(name_a, name_b)\n",
    "        # print(union_set)\n",
    "        for key in union_set.keys():\n",
    "            if find(key) != key:\n",
    "                # print(key, find(key))\n",
    "                vals[find(key)] = vals.get(find(key), 0) + vals.get(key, 0)\n",
    "        # print(vals)\n",
    "        return [f\"{key}({val})\" for key, val in vals.items() if union_set.get(key, \"\") == key or key not in union_set]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        namelist = {} #名字列表 名字:[idx,次数]\n",
    "        idx = 0\n",
    "        def check(x,nn):\n",
    "            nonlocal idx\n",
    "            if x not in namelist:\n",
    "                namelist[x]=[idx,nn]\n",
    "                idx+=1\n",
    "        \n",
    "        for s in names:\n",
    "            na,time = s[:-1].split(\"(\")\n",
    "            check(na,int(time))\n",
    "        for s in synonyms:\n",
    "            x,y = s[1:-1].split(\",\")\n",
    "            check(x,0)\n",
    "            check(y,0)\n",
    "        print(namelist)\n",
    "\n",
    "        N = len(namelist)\n",
    "        father = list(range(N))\n",
    "        def find(x):\n",
    "            if x!=father[x]:\n",
    "                father[x]=find(father[x])\n",
    "            return father[x]\n",
    "        def unit(x,y):\n",
    "            fx,fy = find(x),find(y)\n",
    "            if fx<fy:father[fy]=fx\n",
    "            else:father[fx]=fy\n",
    "        for s in synonyms:\n",
    "            x,y = s[1:-1].split(\",\")\n",
    "            unit(namelist[x][0],namelist[y][0])\n",
    "        temp = defaultdict(list)\n",
    "        for k,v in namelist.items():\n",
    "            f = find(v[0])\n",
    "            if not temp[f]:\n",
    "                temp[f].append(v[1])\n",
    "            else:\n",
    "                temp[f][0]+=v[1]\n",
    "            temp[f].append(k)\n",
    "        print(temp)\n",
    "        return [sorted(arr[1:])[0]+\"(\"+str(arr[0])+\")\" for arr in temp.values()]\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        p=dict()\n",
    "        def find(x):\n",
    "            if x!=p.get(x,x):\n",
    "                p[x]=find(p.get(x,x))\n",
    "            return p.get(x,x)\n",
    "        for x in synonyms:\n",
    "            s=x.split(',')\n",
    "            a,b=s[0][1:],s[1][:-1]\n",
    "            pa,pb=find(a),find(b)\n",
    "            if pa<pb:\n",
    "                p[pb]=pa\n",
    "            else:\n",
    "                p[pa]=pb\n",
    "        ans=dict()\n",
    "        for s in names:\n",
    "            x,y=s.split('(')\n",
    "            y=int(y[:-1])\n",
    "            px=find(x)\n",
    "            if px in ans:\n",
    "                ans[px]+=y\n",
    "            else:\n",
    "                ans[px]=y\n",
    "        res=[]\n",
    "        for k,v in ans.items():\n",
    "            res.append(\"{}({})\".format(k,v))\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        org_name_dic = {}\n",
    "        org_name_set = set()\n",
    "        for name_num in names:\n",
    "            lis = name_num.split('(')\n",
    "            name = lis[0]\n",
    "            num = int(lis[1][:-1])\n",
    "            org_name_dic[name] = num\n",
    "            org_name_set.add(name)\n",
    "        edge_lis = collections.defaultdict(set)\n",
    "        for syn in synonyms:\n",
    "            tup_lis = syn.split(',')\n",
    "            name1 = tup_lis[0][1:]\n",
    "            name2 = tup_lis[1][:-1]\n",
    "            if name1 not in org_name_set:\n",
    "                org_name_set.add(name1)\n",
    "                org_name_dic[name1] = 0\n",
    "            if name2 not in org_name_set:\n",
    "                org_name_set.add(name2)\n",
    "                org_name_dic[name2] = 0\n",
    "            edge_lis[name1].add(name2)\n",
    "            edge_lis[name2].add(name1)\n",
    "        #print(org_name_set)\n",
    "        ret_dic = []\n",
    "        while len(org_name_set) > 0:\n",
    "            cur_flag = org_name_set.pop()\n",
    "            cur_count = org_name_dic[cur_flag]\n",
    "            cur_q = [cur_flag]\n",
    "            while len(cur_q) > 0:\n",
    "                top = cur_q.pop(0)\n",
    "                #print(top, edge_lis[top])\n",
    "                for e in edge_lis[top]:\n",
    "                    if e in org_name_set:\n",
    "                        org_name_set.remove(e)\n",
    "                        cur_count += org_name_dic[e]\n",
    "                        cur_q.append(e)\n",
    "                        if e < cur_flag:\n",
    "                            cur_flag = e\n",
    "                    #print(cur_q)\n",
    "            ret_dic.append(\"{}({})\".format(cur_flag, cur_count))\n",
    "        return ret_dic\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        HashTable = defaultdict(int)\n",
    "        for i in range(len(names)):\n",
    "            for j in range(len(names[i])-1,-1,-1):\n",
    "                if names[i][j] == \"(\":\n",
    "                    head = names[i][:j]\n",
    "                    count = names[i][j+1:len(names[i])-1]\n",
    "                    HashTable[head] = int(count)\n",
    "\n",
    "        djs = defaultdict(int)\n",
    "        def find(x:str)->str:\n",
    "            if djs[x] == 0:\n",
    "                djs[x] = x\n",
    "                return djs[x]\n",
    "            if djs[x] != x:\n",
    "                djs[x] = find(djs[x])\n",
    "            return djs[x]\n",
    "        def union(x:str,y:str)->None:\n",
    "            djs[find(x)] = find(y)\n",
    "\n",
    "        for strr in synonyms:\n",
    "            for j in range(len(strr)):\n",
    "                if strr[j] == \",\":\n",
    "                    name1 = strr[1:j]\n",
    "                    name2 = strr[j+1:len(strr)-1]\n",
    "                    if find(name1) < find(name2):\n",
    "                        HashTable[find(name1)] = HashTable[find(name1)] + HashTable[find(name2)]\n",
    "                        HashTable[find(name2)] = 0\n",
    "                        union(name2,name1)\n",
    "                    elif find(name1) > find(name2):\n",
    "                        HashTable[find(name2)] = HashTable[find(name1)] + HashTable[find(name2)]\n",
    "                        HashTable[find(name1)] = 0\n",
    "                        union(name1,name2)\n",
    "\n",
    "        ans=[]\n",
    "        for key , val in HashTable.items():\n",
    "            if val > 0:\n",
    "                strr = key +\"(\" + str(val) + \")\"\n",
    "                ans.append(strr)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        mer = {}\n",
    "        def find(name1):\n",
    "            return name1 if name1 not in mer or mer[name1] == name1 else find(mer[name1]) \n",
    "        def merge(name1,name2):\n",
    "            if name1 not in mer:\n",
    "                mer[name1] = name1\n",
    "            if name2 not in mer:\n",
    "                mer[name2] = name2\n",
    "            n_root_1,n_root_2 = find(name1),find(name2)\n",
    "            if n_root_1>n_root_2:\n",
    "                mer[n_root_1] = n_root_2\n",
    "            else:\n",
    "                mer[n_root_2] = n_root_1\n",
    "        for sy in synonyms:\n",
    "            le = len(sy)\n",
    "            sy = sy[1:le-1]\n",
    "            nams = sy.split(\",\")\n",
    "            merge(nams[0],nams[1])\n",
    "        res_map = {}\n",
    "        for name in names:\n",
    "            real_name,nu = name.split(\"(\")\n",
    "            name_root = find(real_name)\n",
    "            num = int(nu[:-1])\n",
    "            res_map[name_root] =  num if name_root not in res_map else res_map[name_root]+num\n",
    "        res = []\n",
    "        for key in res_map.keys():\n",
    "             res.append(key+'('+str(res_map[key])+')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0  for _ in range(n)]\n",
    "        \n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "        \n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        xroot, yroot = self.find(x), self.find(y)\n",
    "        if xroot != yroot:\n",
    "            if self.rank[xroot] < self.rank[yroot]:\n",
    "                xroot, yroot = yroot, xroot\n",
    "            self.parent[yroot] = xroot\n",
    "            if self.rank[xroot] == self.rank[yroot]:\n",
    "                self.rank[xroot] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        nameset = set()\n",
    "        graph = defaultdict(set)\n",
    "        for syn in synonyms:\n",
    "            syn = syn[1: -1]\n",
    "            u, v = syn.split(',')\n",
    "            nameset.add(u)\n",
    "            nameset.add(v)\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "            \n",
    "        name2cnt = defaultdict(int)\n",
    "        newnames = set()\n",
    "        for item in names:\n",
    "            item = item[: -1]\n",
    "            name, cnt = item.split('(')\n",
    "            name2cnt[name] = int(cnt)\n",
    "            nameset.add(name)\n",
    "            newnames.add(name)\n",
    "            \n",
    "        name2idx = {\n",
    "            name: idx\n",
    "            for idx, name\n",
    "            in enumerate(nameset)\n",
    "        }\n",
    "        idx2name = {\n",
    "            idx: name\n",
    "            for idx, name\n",
    "            in enumerate(nameset)\n",
    "        }\n",
    "        \n",
    "        n = len(nameset)\n",
    "        ufs = UnionFindSet(n)\n",
    "        for u, vset in graph.items():\n",
    "            i = name2idx[u]\n",
    "            for v in vset:\n",
    "                j = name2idx[v]\n",
    "                ufs.union(i, j)\n",
    "                \n",
    "        components = defaultdict(set)\n",
    "        for name in newnames:\n",
    "            idx = name2idx[name]\n",
    "            components[ufs.find(idx)].add(name)\n",
    "            \n",
    "        res = []\n",
    "        for component in components.values():\n",
    "            realname = min(component)\n",
    "            cnt = 0\n",
    "            for name in component:\n",
    "                cnt += name2cnt[name]\n",
    "                \n",
    "            item = realname + '(' + str(cnt) + ')'\n",
    "            res.append(item)\n",
    "            \n",
    "        return res\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        hash = {}\n",
    "        hash2 = {}\n",
    "        h = 0\n",
    "        \n",
    "        for syn in synonyms:\n",
    "            i = 1\n",
    "            n1, n2 = \"\", \"\"\n",
    "            while syn[i] != ',':\n",
    "                n1 = n1 + syn[i]\n",
    "                i += 1\n",
    "            i += 1\n",
    "            while syn[i] != ')':\n",
    "                n2 = n2 + syn[i]\n",
    "                i += 1\n",
    "            if n1 not in hash:\n",
    "                hash[n1] = h\n",
    "                hash2[h] = n1\n",
    "                h += 1\n",
    "            if n2 not in hash:\n",
    "                hash[n2] = h\n",
    "                hash2[h] = n2\n",
    "                h += 1\n",
    "        \n",
    "        dic = {}\n",
    "        for k in hash:\n",
    "            dic[k] = 0\n",
    "        for s in names:\n",
    "            i = 0\n",
    "            name = \"\"\n",
    "            while i < len(s):\n",
    "                while s[i] != '(':\n",
    "                    name = name + s[i]\n",
    "                    i += 1\n",
    "                i += 1\n",
    "                cnt = 0\n",
    "                while s[i] != ')':\n",
    "                    cnt = cnt * 10 + int(s[i])\n",
    "                    i += 1\n",
    "                i += 1\n",
    "            dic[name] = cnt\n",
    "            h += 1\n",
    "        # print(dic)\n",
    "\n",
    "        fa = [i for i in range(h)]\n",
    "\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx == fy:\n",
    "                return\n",
    "            if hash2[fx] > hash2[fy]:\n",
    "                fx, fy = fy, fx\n",
    "            fa[fy] = fx\n",
    "            dic[hash2[fx]] += dic[hash2[fy]]\n",
    "            del dic[hash2[fy]]\n",
    "        \n",
    "        for syn in synonyms:\n",
    "            i = 1\n",
    "            n1, n2 = \"\", \"\"\n",
    "            while syn[i] != ',':\n",
    "                n1 = n1 + syn[i]\n",
    "                i += 1\n",
    "            i += 1\n",
    "            while syn[i] != ')':\n",
    "                n2 = n2 + syn[i]\n",
    "                i += 1\n",
    "            if n1 in hash and n2 in hash:\n",
    "                union(hash[n1], hash[n2])\n",
    "        \n",
    "        # print(dic)\n",
    "        for k, v in dic.items():\n",
    "            ans.append(k + \"(\" + str(v) + \")\")\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "\n",
    "        names = sorted([tuple(x[:-1].split('(')) for x in names])\n",
    "        synonyms = [x[1:-1].split(',') for x in synonyms]\n",
    "\n",
    "        all_names = set()\n",
    "        for s, t in synonyms:\n",
    "            all_names.add(s)\n",
    "            all_names.add(t)\n",
    "        for x, _ in names:\n",
    "            all_names.add(x)\n",
    "\n",
    "        sorted_names = sorted(all_names)\n",
    "        name_to_id = {name: i for i, name in enumerate(sorted_names)}\n",
    "        parents = list(range(len(sorted_names)))\n",
    "\n",
    "        def find(p):\n",
    "            if p != parents[p]:\n",
    "                parents[p] = find(parents[p])\n",
    "            return parents[p]\n",
    "\n",
    "        def connect(p, q):\n",
    "            r1, r2 = find(p), find(q)\n",
    "            if r1 < r2:\n",
    "                parents[r2] = r1\n",
    "            elif r1 > r2:\n",
    "                parents[r1] = r2\n",
    "\n",
    "        for s, t in synonyms:\n",
    "            p = name_to_id[s]\n",
    "            q = name_to_id[t]\n",
    "            connect(p, q)\n",
    "\n",
    "        ans = defaultdict(int)\n",
    "        for name, cnt in names:\n",
    "            idx = name_to_id[name]\n",
    "            root_name = sorted_names[find(idx)]\n",
    "            ans[root_name] += int(cnt)\n",
    "\n",
    "        ans = [f'{name}({total})' for name, total in ans.items()]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        def judgeorder(name1, name2):\n",
    "            border = min(len(name1), len(name2))\n",
    "            i = 0\n",
    "            ret = name1\n",
    "            while i < border:\n",
    "                if ord(name1[i]) == ord(name2[i]):\n",
    "                    i += 1\n",
    "                else:\n",
    "                    if ord(name2[i]) < ord(name1[i]):\n",
    "                        ret = name2\n",
    "                    break\n",
    "            return ret\n",
    "\n",
    "        def find(x):\n",
    "            if father[x] == x:\n",
    "                return x\n",
    "            else:\n",
    "                return find(father[x])\n",
    "\n",
    "\n",
    "\n",
    "        def merge(name1, name2):\n",
    "            index1, index2 = orderdict[name1], orderdict[name2]\n",
    "            x, y = find(index1), find(index2)\n",
    "            if x == y:\n",
    "                return\n",
    "            else:\n",
    "                name1, name2 = list(orderdict.keys())[x], list(orderdict.keys())[y]\n",
    "                root = judgeorder(name1, name2)\n",
    "                son = name1 if root != name1 else name2\n",
    "                father[orderdict[son]] = orderdict[root]\n",
    "                namedict[root] += namedict[son]\n",
    "\n",
    "\n",
    "        namedict = collections.defaultdict(int)\n",
    "        orderdict = collections.defaultdict(int)\n",
    "        for i , name in enumerate(names):\n",
    "            nameindex, temp  =name.split(\"(\")\n",
    "            value, _ = temp.split(\")\")\n",
    "            namedict[nameindex] = int(value)\n",
    "            orderdict[nameindex] = i\n",
    "        father = [i for i in range(len(names))]\n",
    "\n",
    "        for k in synonyms:\n",
    "            name1, name2 = k.strip(\"()\").split(\",\")\n",
    "            merge(name1, name2)\n",
    "\n",
    "        return  [name + \"(\" + str(value) + \")\" for name, value in namedict.items() if orderdict[name] == father[orderdict[name]]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "\n",
    "        name_cnt = {}\n",
    "        for i in range(len(names)):\n",
    "            name = names[i].split(\"(\")[0]\n",
    "            cnt = int(names[i].split(\"(\")[1][:-1])\n",
    "\n",
    "            name_cnt[name] = cnt\n",
    "\n",
    "        name_pair = set()\n",
    "        for i in range(len(synonyms)):\n",
    "            name1 = synonyms[i].split(\",\")[0][1:]\n",
    "            name2 = synonyms[i].split(\",\")[1][:-1]\n",
    "\n",
    "            if name1 == name2:\n",
    "                continue\n",
    "\n",
    "            if name1 > name2:\n",
    "                name1, name2 = name2, name1\n",
    "            \n",
    "\n",
    "            if (name1, name2) not in name_pair:\n",
    "                name_pair.add((name1, name2))\n",
    "            \n",
    "\n",
    "            if name1 not in name_cnt:\n",
    "                name_cnt[name1] = 0\n",
    "            \n",
    "            if name2 not in name_cnt:\n",
    "                name_cnt[name2] = 0\n",
    "\n",
    "\n",
    "        father = {}\n",
    "        for name in name_cnt:\n",
    "            father[name] = name\n",
    "\n",
    "        def find(x):\n",
    "\n",
    "            return x if father[x] == x else find(father[x])\n",
    "        \n",
    "        def merge(x, y):\n",
    "            f_x = find(x); f_y = find(y)\n",
    "            s = f_x if f_x < f_y else f_y\n",
    "\n",
    "            while x != f_x:\n",
    "                tmp = father[x]\n",
    "                father[x] = s\n",
    "                x = tmp\n",
    "            # father[x] = s\n",
    "\n",
    "            while y != f_y:\n",
    "                tmp = father[y]\n",
    "                father[y] = s\n",
    "                y = tmp\n",
    "\n",
    "            father[f_x] = s; father[f_y] = s \n",
    "\n",
    "\n",
    "        for name1, name2 in name_pair:\n",
    "            f_name1 = find(name1)\n",
    "            f_name2 = find(name2)\n",
    "\n",
    "            merge(name1, name2)\n",
    "\n",
    "            s = f_name1 if f_name1 < f_name2 else f_name2\n",
    "\n",
    "            if f_name1 != f_name2:\n",
    "                name_cnt[s] = name_cnt[f_name1] + name_cnt[f_name2]\n",
    "\n",
    "        res = []\n",
    "        for name in name_cnt:\n",
    "            if father[name] == name:\n",
    "                res.append(\"{}({})\".format(name, name_cnt[name]))\n",
    "\n",
    "        # rrr = [\"Gsiiyo(215)\",\"Adlue(171)\",\"Iggrg(99)\",\"Umt(13)\",\"Bbcpth(256)\",\"Jxv(152)\",\"Vqnjg(142)\",\"Bvnkk(52)\",\"Bcs(262)\",\"Alqw(424)\",\"Kmrev(31)\",\"Bjfkzo(54)\",\"Oip(13)\",\"Qlvglt(36)\",\"Clplqf(8)\",\"Aasipa(262)\",\"Sfjdjc(62)\",\"Ccqunq(186)\",\"Oyo(32)\",\"Zhc(44)\",\"Fayxe(155)\",\"Ndc(62)\",\"Wzt(41)\",\"Xioal(11)\",\"Mqgga(31)\",\"Jpftyg(96)\",\"Fshi(62)\",\"Lnow(157)\",\"Rmlbnj(98)\",\"Ghk(14)\",\"Jylbla(100)\",\"Fzoe(130)\",\"Orpqim(69)\",\"Jnij(75)\",\"Jmqqsj(19)\",\"Kaaht(28)\",\"Ttj(28)\",\"Xuzubb(90)\",\"Dma(170)\",\"Slfwyo(82)\",\"Gaoo(98)\",\"Lwyfn(50)\",\"Pxzfjg(91)\",\"Gql(67)\",\"Sqwejn(19)\",\"Xbesji(70)\",\"Mrqlne(39)\",\"Ghlj(35)\",\"Rqa(117)\",\"Uwy(26)\",\"Prf(48)\",\"Axaqkm(100)\",\"Npbu(62)\",\"Kxjw(36)\",\"Zvzm(31)\",\"Icsvku(1)\",\"Phlto(41)\",\"Vaakt(21)\",\"Slh(66)\"]\n",
    "        \n",
    "        # for nn in rrr:\n",
    "        #     if nn not in res:\n",
    "        #         print(\"nonono: {}\".format(nn))\n",
    "        \n",
    "        # for nn in res:\n",
    "        #     if nn not in rrr:\n",
    "        #         print(\"nonono2: {}\".format(nn))\n",
    "\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        name_map={}\n",
    "        def dfs(x):\n",
    "            name_map.setdefault(x,x)\n",
    "            if x!=name_map[x]:\n",
    "                name_map[x]=dfs(name_map[x])\n",
    "            return name_map[x]\n",
    "        def union(x,y):\n",
    "            name_map[x]=dfs(x)\n",
    "            name_map[y]=dfs(y)\n",
    "            if name_map[x]<name_map[y]:\n",
    "                name_map[name_map[y]]=name_map[x]\n",
    "            else:\n",
    "                name_map[name_map[x]]=name_map[y]\n",
    "        for name_pair in synonyms:\n",
    "            name_pair = name_pair[1:-1].split(',')\n",
    "            name1 = name_pair[0]\n",
    "            name2 = name_pair[1]\n",
    "\n",
    "            union(name1, name2)\n",
    "        ans = []\n",
    "        occur_map = {}\n",
    "        for idx, name_cnt in enumerate(names):\n",
    "            name_and_cnt = name_cnt[:-1].split('(')\n",
    "            name = name_and_cnt[0]\n",
    "            cnt = int(name_and_cnt[1])\n",
    "            \n",
    "            #name_map[name] = name\n",
    "            #dfs(name)\n",
    "            if name not in name_map:\n",
    "                name_map[name] = name\n",
    "            else:\n",
    "                name_map[name] = dfs(name) # dfs 搜索 father，因为可能会追溯到更新后的father\n",
    "            \n",
    "            if name_map[name] not in occur_map:\n",
    "                occur_map[name_map[name]] = len(ans)\n",
    "                ans.append((name_map[name], cnt))\n",
    "            else:\n",
    "                last_cnt = ans[occur_map[name_map[name]]][1]\n",
    "\n",
    "                ans[occur_map[name_map[name]]] = (name_map[name], last_cnt+ cnt)\n",
    "        for i, x in enumerate(ans):\n",
    "            ans[i] = x[0] + '(' + str(x[1]) + ')'\n",
    "             \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        mps = dict()\n",
    "        p = dict()\n",
    "        for name in names:\n",
    "            mps[name.split('(')[0]] = int(name.split('(')[1].split(')')[0])\n",
    "            p[name.split('(')[0]] = None\n",
    "        name_pairs = []\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym.split(',')[0][1:], synonym.split(',')[1][:-1]\n",
    "            p[name1], p[name2] = None, None\n",
    "            name_pairs.append([name1, name2])\n",
    "        def find(x):\n",
    "            if p[x] == None: return x\n",
    "            p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        for name_pair in name_pairs:\n",
    "            name1, name2 = name_pair[0], name_pair[1]\n",
    "            pname1 = find(name1)\n",
    "            pname2 = find(name2)\n",
    "            if pname1 < pname2:\n",
    "                p[pname2] = pname1\n",
    "            elif pname1 > pname2:\n",
    "                p[pname1] = pname2\n",
    "        tmp = dict()\n",
    "        for (k, v) in mps.items():\n",
    "            pname = find(k)\n",
    "            if pname in tmp:\n",
    "                tmp[pname] += v\n",
    "            else:\n",
    "                tmp[pname] = v\n",
    "        ans = []\n",
    "        for (k,v) in tmp.items():\n",
    "            ans.append(f\"{k}({v})\")\n",
    "        return ans\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        \"\"\"\n",
    "        并查集常规做法用数组表示每个元素的归属，这里名字是字符串用字典比较合适\n",
    "        Time: O(n), Space: O(n)\n",
    "        \"\"\"\n",
    "\n",
    "        dic = {}\n",
    "        f = {}\n",
    "\n",
    "        for x in names:\n",
    "            name, cnt = x.split('(')\n",
    "            cnt = int(cnt.strip(')'))\n",
    "            dic[name] = cnt\n",
    "        # print(\"所有名字出现的频率字典\", dic)\n",
    "\n",
    "        for x in synonyms:\n",
    "            for t in x.strip('()').split(','):\n",
    "                f[t] = t\n",
    "        # print(\"名字之间有关系的对象（去重），这里可能不全部包括dic所有名字\", f)\n",
    "\n",
    "        def find_leader(v):  # 找boos\n",
    "            if v == f[v]:\n",
    "                return v\n",
    "            return find_leader(f[v])\n",
    "\n",
    "        # 遍历名字之间的关系\n",
    "        for x in synonyms:\n",
    "            [l, r] = x.strip('()').split(',')\n",
    "            a, b = find_leader(l), find_leader(r)\n",
    "            MIN, MAX = min(a, b), max(a, b)\n",
    "            # print(\"找到两个名字的boos 字典序小的一个\", l, r, MIN)\n",
    "            f[MAX] = MIN  # 让大的归顺小的\n",
    "\n",
    "            # 根据先前提供的信息两者已经划分到了同一个boos 已经联系起来了，不要再次做累加操作\n",
    "            # 普通的并查集的归顺操作做两次并不影响，但这里的累加操作不可以重复\n",
    "            if MIN == MAX:\n",
    "                continue\n",
    "            dic[MIN] += dic.get(MAX, 0)  # 把大的频率累加到boos上\n",
    "        # print(\"最终所有名字出现的频率，包括累加\", dic)\n",
    "        # print(\"所有名字归顺完成之后的状态\", f)\n",
    "\n",
    "        # 转成要求的输出格式\n",
    "        ans = []\n",
    "        for x in dic:\n",
    "            if x not in f or x == f[x]:\n",
    "                ans.append(f\"{x}({dic[x]})\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "\n",
    "        dic = {}\n",
    "        f = {}\n",
    "\n",
    "        for x in names:\n",
    "            name, cnt = x.split('(')\n",
    "            cnt = int(cnt.strip(')'))\n",
    "            dic[name] = cnt\n",
    "        # print(\"所有名字出现的频率字典\", dic)\n",
    "\n",
    "        for x in synonyms:\n",
    "            for t in x.strip('()').split(','):\n",
    "                f[t] = t\n",
    "        # print(\"名字之间有关系的对象（去重），这里可能不全部包括dic所有名字\", f)\n",
    "\n",
    "        def find_leader(v):  # 找boos\n",
    "            if v == f[v]:\n",
    "                return v\n",
    "            return find_leader(f[v])\n",
    "\n",
    "        # 遍历名字之间的关系\n",
    "        for x in synonyms:\n",
    "            [l, r] = x.strip('()').split(',')\n",
    "            a, b = find_leader(l), find_leader(r)\n",
    "            MIN, MAX = min(a, b), max(a, b)\n",
    "            # print(\"找到两个名字的boos 字典序小的一个\", l, r, MIN)\n",
    "            f[MAX] = MIN  # 让大的归顺小的\n",
    "\n",
    "            # 根据先前提供的信息两者已经划分到了同一个boos 已经联系起来了，不要再次做累加操作\n",
    "            # 普通的并查集的归顺操作做两次并不影响，但这里的累加操作不可以重复\n",
    "            if MIN == MAX:\n",
    "                continue\n",
    "            dic[MIN] += dic.get(MAX, 0)  # 把大的频率累加到boos上\n",
    "        # print(\"最终所有名字出现的频率，包括累加\", dic)\n",
    "        # print(\"所有名字归顺完成之后的状态\", f)\n",
    "\n",
    "        # 转成要求的输出格式\n",
    "        ans = []\n",
    "        for x in dic:\n",
    "            if x not in f or x == f[x]:\n",
    "                ans.append(f\"{x}({dic[x]})\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "\n",
    "        dic = {}\n",
    "        f = {}\n",
    "\n",
    "        for x in names:\n",
    "            name, cnt = x.split('(')\n",
    "            cnt = int(cnt.strip(')'))\n",
    "            dic[name] = cnt\n",
    "        print(\"所有名字出现的频率字典\", dic)\n",
    "\n",
    "        for x in synonyms:\n",
    "            for t in x.strip('()').split(','):\n",
    "                f[t] = t\n",
    "        print(\"名字之间有关系的对象（去重），这里可能不全部包括dic所有名字\", f)\n",
    "\n",
    "        def find_leader(v):  # 找boos\n",
    "            if v == f[v]:\n",
    "                return v\n",
    "            return find_leader(f[v])\n",
    "        \n",
    "# \"\"\"\n",
    "#         for s in synonyms:\n",
    "#             name1, name2 = s[1:-1].split(\",\")\n",
    "#             # 不存在的话 仍然需要在f和cnt里进行增加 因为连接关系仍有用\n",
    "#             if name1 not in f:\n",
    "#                 f[name1] = name1\n",
    "#                 cnt[name1] = 0\n",
    "#             if name2 not in f:\n",
    "#                 f[name2] = name2\n",
    "#                 cnt[name2] = 0\n",
    "#             p1, p2 = find(name1), find(name2)\n",
    "#             if p1 == p2:\n",
    "#                 # 父亲一样 那么此时什么都不做\n",
    "#                 continue\n",
    "#             # 父亲不一样 需要合并 字典序小的作为父亲\n",
    "#             freq = cnt[p1] + cnt[p2]\n",
    "#             fa = min(p1, p2)\n",
    "#             ch = max(p1, p2)\n",
    "#             f[ch] = fa\n",
    "#             cnt[ch] = 0\n",
    "#             cnt[fa] = freq\n",
    "# \"\"\"\n",
    "\n",
    "        # 遍历名字之间的关系\n",
    "        for x in synonyms:\n",
    "            [l, r] = x.strip('()').split(',')\n",
    "            a, b = find_leader(l), find_leader(r)\n",
    "            MIN, MAX = min(a, b), max(a, b)\n",
    "            print(\"找到两个名字的boos 字典序小的一个\", l, r, MIN)\n",
    "            f[MAX] = MIN  # 让大的归顺小的\n",
    "\n",
    "            # 根据先前提供的信息两者已经划分到了同一个boos 已经联系起来了，不要再次做累加操作\n",
    "            # 普通的并查集的归顺操作做两次并不影响，但这里的累加操作不可以重复\n",
    "            if MIN == MAX:\n",
    "                continue\n",
    "            dic[MIN] += dic.get(MAX, 0)  # 把大的频率累加到boos上\n",
    "        print(\"最终所有名字出现的频率，包括累加\", dic)\n",
    "        print(\"所有名字归顺完成之后的状态\", f)\n",
    "\n",
    "        # 转成要求的输出格式\n",
    "        ans = []\n",
    "        for x in dic:\n",
    "            if x not in f or x == f[x]:\n",
    "                ans.append(f\"{x}({dic[x]})\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        # synonyms.sort()\n",
    "        synonyms_pair = []\n",
    "        parents = {}\n",
    "        weights = {}\n",
    "        for s in synonyms:\n",
    "            i1 = s.find(\"(\")\n",
    "            i2 = s.find(\",\")\n",
    "            i3 = s.find(\")\")\n",
    "            a = s[i1+1:i2]\n",
    "            b = s[i2+1:i3]\n",
    "            synonyms_pair.append([a,b])\n",
    "            parents[a] = a\n",
    "            parents[b] = b\n",
    "        for s in names:\n",
    "            i1 = s.find(\"(\")\n",
    "            i2 = s.find(\")\")\n",
    "            parents[s[0:i1]] = s[0:i1]\n",
    "            weights[s[0:i1]] = int(s[i1+1:i2])\n",
    "        def find(x):\n",
    "            if(x!=parents[x]):\n",
    "                parents[x] = find(parents[x])\n",
    "            return parents[x]\n",
    "        def union(x,y):\n",
    "            ax = find(x)\n",
    "            ay = find(y)\n",
    "            if(ax < ay):\n",
    "                parents[ay] = ax\n",
    "            else:\n",
    "                parents[ax] = ay\n",
    "            return\n",
    "        result = {}\n",
    "        for [x,y] in synonyms_pair:\n",
    "            union(x,y)\n",
    "        for x in weights:\n",
    "            ax = find(x)\n",
    "            ay = find(y)\n",
    "            if(ax not in result):\n",
    "                result[ax] = weights[x]\n",
    "            else:\n",
    "                result[ax] += weights[x]\n",
    "        ans = []\n",
    "        print(parents)\n",
    "        for k,v in result.items():\n",
    "            ans.append(k+\"(\"+str(v)+\")\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "\n",
    "        dic = {}\n",
    "        f = {}\n",
    "\n",
    "        for x in names:\n",
    "            name, cnt = x.split('(')\n",
    "            cnt = int(cnt.strip(')'))\n",
    "            dic[name] = cnt\n",
    "        print(\"所有名字出现的频率字典\", dic)\n",
    "\n",
    "        for x in synonyms:\n",
    "            for t in x.strip('()').split(','):\n",
    "                f[t] = t\n",
    "        print(\"名字之间有关系的对象（去重），这里可能不全部包括dic所有名字\", f)\n",
    "\n",
    "        def find_leader(v):  # 找boos\n",
    "            if v == f[v]:\n",
    "                return v\n",
    "            return find_leader(f[v])\n",
    "        \n",
    "# \"\"\"\n",
    "#         for s in synonyms:\n",
    "#             name1, name2 = s[1:-1].split(\",\")\n",
    "#             # 不存在的话 仍然需要在f和cnt里进行增加 因为连接关系仍有用\n",
    "#             if name1 not in f:\n",
    "#                 f[name1] = name1\n",
    "#                 cnt[name1] = 0\n",
    "#             if name2 not in f:\n",
    "#                 f[name2] = name2\n",
    "#                 cnt[name2] = 0\n",
    "#             p1, p2 = find(name1), find(name2)\n",
    "#             if p1 == p2:\n",
    "#                 # 父亲一样 那么此时什么都不做\n",
    "#                 continue\n",
    "#             # 父亲不一样 需要合并 字典序小的作为父亲\n",
    "#             freq = cnt[p1] + cnt[p2]\n",
    "#             fa = min(p1, p2)\n",
    "#             ch = max(p1, p2)\n",
    "#             f[ch] = fa\n",
    "#             cnt[ch] = 0\n",
    "#             cnt[fa] = freq\n",
    "# \"\"\"\n",
    "\n",
    "        # 遍历名字之间的关系\n",
    "        for x in synonyms:\n",
    "            [l, r] = x.strip('()').split(',')\n",
    "            a, b = find_leader(l), find_leader(r)\n",
    "            MIN, MAX = min(a, b), max(a, b)\n",
    "            print(\"找到两个名字的boos 字典序小的一个\", l, r, MIN)\n",
    "\n",
    "            if MIN == MAX:\n",
    "                continue\n",
    "\n",
    "            f[MAX] = MIN  # 让大的归顺小的\n",
    "            dic[MIN] += dic.get(MAX, 0)  # 把大的频率累加到boos上\n",
    "        print(\"最终所有名字出现的频率，包括累加\", dic)\n",
    "        print(\"所有名字归顺完成之后的状态\", f)\n",
    "\n",
    "        # 转成要求的输出格式\n",
    "        ans = []\n",
    "        for x in dic:\n",
    "            if x not in f or x == f[x]:\n",
    "                ans.append(f\"{x}({dic[x]})\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        n=len(names)\n",
    "        graph=[[] for _ in range(100000)]    #建图\n",
    "        cnt=[]\n",
    "        name_id=dict()\n",
    "        id_name=[]\n",
    "        index=0\n",
    "        for id,name in enumerate(names):\n",
    "            i=0\n",
    "            while name[i]!=\"(\":\n",
    "                i+=1\n",
    "            cnt.append(int(name[i+1:-1]))\n",
    "            name_id[name[:i]]=id\n",
    "            id_name.append(name[:i])\n",
    "        for syno in synonyms:\n",
    "            syn=syno.split(\",\")\n",
    "            syn[0]=syn[0][1:]\n",
    "            syn[1]=syn[1][:-1]\n",
    "            if syn[0] not in name_id.keys():\n",
    "                name_id[syn[0]]=len(id_name)\n",
    "                id_name.append(syn[0])\n",
    "                cnt.append(0)\n",
    "            if syn[1] not in name_id.keys():\n",
    "                name_id[syn[1]]=len(id_name)\n",
    "                id_name.append(syn[1])\n",
    "                cnt.append(0)\n",
    "            graph[name_id[syn[0]]].append(name_id[syn[1]])\n",
    "            graph[name_id[syn[1]]].append(name_id[syn[0]])\n",
    "        ans=[]\n",
    "        visited=[0]*100000\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                name=\"\"\n",
    "                count=0\n",
    "                queue=[i]\n",
    "                visited[i]=1\n",
    "                while queue:\n",
    "                    tmp=queue.pop(0)\n",
    "                    if not name or name>id_name[tmp]:\n",
    "                        name=id_name[tmp]\n",
    "                    count+=cnt[tmp]\n",
    "                    # print(count)\n",
    "                    for v in graph[tmp]:\n",
    "                        if not visited[v]:\n",
    "                            visited[v]=1\n",
    "                            queue.append(v)\n",
    "                    # print(queue)\n",
    "                ans.append(name+\"(\"+str(count)+\")\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        def find_top(n):\n",
    "            if isinstance(name_d[n], int):\n",
    "                return n\n",
    "            top = find_top(name_d[n])\n",
    "            name_d[n] = top\n",
    "            return top\n",
    "\n",
    "        name_d = {}\n",
    "        for l in names:\n",
    "            sub = l.split(\"(\")\n",
    "            name_d[sub[0]] = int(sub[1][:-1])\n",
    "\n",
    "        for l in synonyms:\n",
    "            n = l[1:-1].split(\",\")\n",
    "            if n[0] not in name_d:\n",
    "                name_d[n[0]] = 0\n",
    "            if n[1] not in name_d:\n",
    "                name_d[n[1]] = 0\n",
    "            n[0] = find_top(n[0])\n",
    "            n[1] = find_top(n[1])\n",
    "            if n[0]  == n[1]:\n",
    "                continue\n",
    "            if n[0] > n[1]:\n",
    "                n[0], n[1] = n[1], n[0]\n",
    "            name_d[n[0]] += name_d[n[1]]\n",
    "            name_d[n[1]] = n[0]\n",
    "        \n",
    "        res = []\n",
    "        for n,count in name_d.items():\n",
    "            if isinstance(count, int):\n",
    "                res.append(\"%s(%d)\" % (n, count))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        \n",
    "        class UninoFind:\n",
    "            def __init__(self,n):\n",
    "                self.parent = [i for i in range(n)]\n",
    "            \n",
    "            def find(self,x):\n",
    "                while x!=self.parent[x]:\n",
    "                    self.parent[x] = self.parent[self.parent[x]]\n",
    "                    x = self.parent[x]\n",
    "                return x\n",
    "            \n",
    "            def union(self,x,y):\n",
    "                p_x = self.find(x)\n",
    "                p_y = self.find(y)\n",
    "                if p_x!=p_y:\n",
    "                    if index2name[p_x]<index2name[p_y]:\n",
    "                        self.parent[p_y] = p_x \n",
    "                    else:\n",
    "                        self.parent[p_x] = p_y \n",
    "        n = len(synonyms)*2\n",
    "        \n",
    "        m = len(names)\n",
    "        uf = UninoFind(max(m,n))\n",
    "        name2index = {}\n",
    "        index2name = {}\n",
    "        for i,name in enumerate(names):\n",
    "            end_index = name.rfind('(')\n",
    "            mz = name[:end_index]\n",
    "            number = int(name[end_index+1:len(name)-1])\n",
    "            name2index[mz] = [i,number]\n",
    "            index2name[i]=mz\n",
    "        for synonym in synonyms:\n",
    "            mid_index = synonym.find(',')\n",
    "            name1 = synonym[1:mid_index]\n",
    "            name2 = synonym[mid_index+1:len(synonym)-1]\n",
    "            if name1 not in name2index:\n",
    "                name2index[name1]=[len(name2index),0]\n",
    "                index2name[len(index2name)]=name1\n",
    "            if name2 not in name2index:\n",
    "                name2index[name2]=[len(name2index),0]\n",
    "                index2name[len(index2name)]=name2\n",
    "            index1,index2 = name2index[name1][0],name2index[name2][0]\n",
    "            uf.union(index2,index1)\n",
    "        res = Counter()\n",
    "        for name in names:\n",
    "            end_index = name.rfind('(')\n",
    "            mz = name[:end_index]\n",
    "            index,num = name2index[mz]\n",
    "            p_index = uf.find(index)\n",
    "            res[index2name[p_index]] += num\n",
    "        ret = []\n",
    "        for name,num in res.items():\n",
    "            ret.append(name+\"(\"+str(num)+\")\")\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        dic = {}\n",
    "        l1 = []\n",
    "        for s in names:\n",
    "            t = s.split('(')\n",
    "            dic[t[0]] = t[0]\n",
    "            l1.append((t[0],int(t[1][:-1])) )     \n",
    "        def find(s1):\n",
    "            if s1 not in dic:\n",
    "                dic[s1] = s1\n",
    "            if s1 == dic[s1]:\n",
    "                return s1\n",
    "            else:\n",
    "                dic[s1] = find(dic[s1])\n",
    "                return dic[s1]\n",
    "\n",
    "        def union(s1,s2):\n",
    "            t1 = find(s1)\n",
    "            t2 = find(s2)\n",
    "            if t1 < t2:\n",
    "                dic[t2] = t1\n",
    "            else:\n",
    "                dic[t1] = t2 \n",
    "        for s in synonyms:\n",
    "            li = s[1:-1].split(',')\n",
    "            union(li[0],li[1])\n",
    "        d2 = {}\n",
    "        #print(\"Vbp\",find(\"Vbp\"),find(find(\"Vbp\")))\n",
    "        #print(\"Om\",find(\"Ommjh\"),dic[\"Vbp\"],dic[\"Ommjh\"],find(\"Vbp\"))\n",
    "        for name, nn in l1:\n",
    "            fa = find(name)\n",
    "            if fa not  in d2:\n",
    "                d2[fa] = nn\n",
    "            else:\n",
    "                d2[fa] += nn\n",
    "        l2 = [name + \"(\" + str(nn)+\")\" for name,nn in d2.items()]\n",
    "        #l2.sort()\n",
    "        return l2\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "\n",
    "        md = {}\n",
    "        d = {}\n",
    "        for name_str in names:\n",
    "            lbi = name_str.find('(')\n",
    "\n",
    "            name = name_str[:lbi]\n",
    "            freq = int(name_str[lbi+1:-1])\n",
    "            d[name] = freq\n",
    "\n",
    "            md[name] = name\n",
    "        \n",
    "        # print(d)\n",
    "\n",
    "        def find_root(name):\n",
    "            assert name in md\n",
    "            father = md[name]\n",
    "            if name == father:\n",
    "                return father\n",
    "            else:\n",
    "                return find_root(father)\n",
    "\n",
    "        for synonym_str in synonyms:\n",
    "            ci = synonym_str.find(',')\n",
    "            name1 = synonym_str[1:ci]\n",
    "            name2 = synonym_str[ci+1:-1]\n",
    "\n",
    "            if name1 not in md and name2 not in md:\n",
    "                md[name1] = name1\n",
    "                md[name2] = name1\n",
    "            elif name1 in md and name2 in md:\n",
    "                md[find_root(name1)] = find_root(name2)\n",
    "            else:\n",
    "                if name1 not in md:\n",
    "                    md[name1] = find_root(name2)\n",
    "                if name2 not in md:\n",
    "                    md[name2] = find_root(name1)\n",
    "        \n",
    "        # print(md)\n",
    "        root_d = {}\n",
    "\n",
    "        # print(md.keys())\n",
    "        # print(d.keys())\n",
    "\n",
    "        for k in md.keys():\n",
    "            root = find_root(k)\n",
    "\n",
    "            # print(f'{k} root: {root}')\n",
    "            if root not in root_d:\n",
    "                root_d[root] = []\n",
    "            \n",
    "            root_d[root].append(k)\n",
    "\n",
    "        ret = []\n",
    "        for _, v in root_d.items():\n",
    "\n",
    "            v.sort()\n",
    "            name = v[0]\n",
    "            count = sum([d.get(x,0) for x in v])\n",
    "\n",
    "            ret.append(f'{name}({count})')\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        n = len(names)\n",
    "        p, sizes = {}, {}\n",
    "            \n",
    "        \n",
    "        def find(x):\n",
    "            return x if x == p[x] else find(p[x])\n",
    "        \n",
    "        def union(x, y):\n",
    "            rootX, rootY = find(x), find(y)\n",
    "            if rootX == rootY:\n",
    "                return\n",
    "            if nameMap[rootX] < nameMap[rootY]:\n",
    "                p[rootY] = rootX\n",
    "                p[y] = rootX\n",
    "                sizes[rootX] += sizes[rootY]\n",
    "            else:\n",
    "                p[rootX] = rootY\n",
    "                p[x] = rootY\n",
    "                sizes[rootY] += sizes[rootX]\n",
    "\n",
    "        idxs, nameMap, idx = {}, {}, n\n",
    "        for i in range(n):\n",
    "            name, cnt = names[i][:-1].split('(')\n",
    "            p[i] = i\n",
    "            sizes[i] = int(cnt)\n",
    "            idxs[name] = i\n",
    "            nameMap[i] = name\n",
    "        \n",
    "        for syn in synonyms:\n",
    "            x, y = syn[1:-1].split(',')\n",
    "            if x not in idxs:\n",
    "                nameMap[idx] = x\n",
    "                sizes[idx] = 0\n",
    "                p[idx] = idx\n",
    "                idxs[x] = idx\n",
    "                idx += 1\n",
    "            if y not in idxs:\n",
    "                nameMap[idx] = y\n",
    "                sizes[idx] = 0\n",
    "                p[idx] = idx\n",
    "                idxs[y] = idx\n",
    "                idx += 1\n",
    "\n",
    "            # print(f'connect: {x}, {y}')\n",
    "            union(idxs[x], idxs[y])\n",
    "\n",
    "        ret = []\n",
    "        # print(p)\n",
    "        for i in range(n):\n",
    "            if p[i] == i:\n",
    "                ret.append(nameMap[i] + '(' + str(sizes[i]) + ')')\n",
    "\n",
    "        return ret\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        f, cnt = {}, {}\n",
    "        for s in names:\n",
    "            x, c = s.split('(')\n",
    "            f[x], cnt[x] = x, int(c[:-1])\n",
    "        \n",
    "        def fd(x):\n",
    "            if f[x] != x: f[x] = fd(f[x]);\n",
    "            return f[x]\n",
    "        \n",
    "        for s in synonyms:\n",
    "            u, v = s.split(',')\n",
    "            if f.get(u[1:]) is None or f.get(v[:-1]) is None: continue\n",
    "            # print(u[1:], v[:-1])\n",
    "            fu, fv = fd(u[1:]), fd(v[:-1])\n",
    "            if fu == fv: continue\n",
    "            if fu < fv:\n",
    "                f[fv] = fu\n",
    "                cnt[fu] += cnt[fv]\n",
    "            else:\n",
    "                f[fu] = fv\n",
    "                cnt[fv] += cnt[fu]\n",
    "        \n",
    "        ret = set()\n",
    "        for x in names:\n",
    "            s = x.split('(')[0]\n",
    "            fs = fd(s)\n",
    "            cur = fs+\"(\"+str(cnt[fs])+\")\"\n",
    "            # print(fs, cnt[fs], cur)\n",
    "            ret.add(cur)\n",
    "        return list(ret)\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        def find(pre_k, k, ks):\n",
    "            if not syn_dic[k]:\n",
    "                return\n",
    "            for w in syn_dic[k]:\n",
    "                if w and w not in ks and w not in syn_dic[pre_k]:\n",
    "                    ks.append(k)\n",
    "                    find(k, w, ks)\n",
    "                    ks.pop()\n",
    "                    if w in name_dic:\n",
    "                        syn_dic[pre_k].append(w)\n",
    "                    syn_dic[w] = None\n",
    "\n",
    "        name_dic = {}\n",
    "        for name in names:\n",
    "            w, n = name.split('(')\n",
    "            name_dic[w] = int(n[:-1])\n",
    "        syn_dic = {}\n",
    "        for s in synonyms:\n",
    "            s1, s2 = s.split(',')\n",
    "            name1 = s1[1:]\n",
    "            name2 = s2[:-1]\n",
    "            if name1 in name_dic or name2 in name_dic:\n",
    "                if name1 not in syn_dic:\n",
    "                    syn_dic[name1] = [name2]\n",
    "                else:\n",
    "                    syn_dic[name1].append(name2)\n",
    "                if name2 not in syn_dic:\n",
    "                    syn_dic[name2] = [name1]\n",
    "                else:\n",
    "                    syn_dic[name2].append(name1)\n",
    "        syn_dic[1] = []\n",
    "        for k in syn_dic:\n",
    "            syn_dic[1] = []\n",
    "            find(1, k, [])\n",
    "\n",
    "        res = []\n",
    "        for k in syn_dic:\n",
    "            if syn_dic[k]:\n",
    "                sub_res = [k] + syn_dic[k]\n",
    "                res.append(sub_res)\n",
    "        for n in res:\n",
    "            i = 0\n",
    "            while n[i] not in name_dic:\n",
    "                i += 1\n",
    "            name = n[i]\n",
    "            for k in n:\n",
    "                if k in name_dic:\n",
    "                    if k < name:\n",
    "                        name_dic[k] += name_dic[name]\n",
    "                        name_dic[name] = -1\n",
    "                        name = k\n",
    "                    elif k > name:\n",
    "                        name_dic[name] += name_dic[k]\n",
    "                        name_dic[k] = -1\n",
    "                    else:\n",
    "                        pass\n",
    "        result = []\n",
    "        for k in name_dic:\n",
    "            if name_dic[k] >= 0:\n",
    "                s = k + '(' + str(name_dic[k]) + ')'\n",
    "                result.append(s)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        def find(pre_k, k, ks):\n",
    "            if not syn_dic[k]:\n",
    "                return\n",
    "            for w in syn_dic[k]:\n",
    "                if w and w not in ks and w not in syn_dic[pre_k]:\n",
    "                    ks.append(k)\n",
    "                    find(k, w, ks)\n",
    "                    ks.pop()\n",
    "                    if w in name_dic:\n",
    "                        syn_dic[pre_k].append(w)\n",
    "                    syn_dic[w] = None\n",
    "\n",
    "        name_dic = {}\n",
    "        for name in names:\n",
    "            w, n = name.split('(')\n",
    "            name_dic[w] = int(n[:-1])\n",
    "        syn_dic = {}\n",
    "        for s in synonyms:\n",
    "            s1, s2 = s.split(',')\n",
    "            name1 = s1[1:]\n",
    "            name2 = s2[:-1]\n",
    "            if name1 in name_dic or name2 in name_dic:\n",
    "                if name1 not in syn_dic:\n",
    "                    syn_dic[name1] = [name2]\n",
    "                else:\n",
    "                    syn_dic[name1].append(name2)\n",
    "                if name2 not in syn_dic:\n",
    "                    syn_dic[name2] = [name1]\n",
    "                else:\n",
    "                    syn_dic[name2].append(name1)\n",
    "        syn_dic[1] = []\n",
    "        for k in syn_dic:\n",
    "            syn_dic[1] = []\n",
    "            find(1, k, [])\n",
    "\n",
    "        res = []\n",
    "        for k in syn_dic:\n",
    "            if syn_dic[k]:\n",
    "                sub_res = [k] + syn_dic[k]\n",
    "                res.append(sub_res)\n",
    "        for n in res:\n",
    "            name = n[0]\n",
    "            for k in n:\n",
    "                if k in name_dic:\n",
    "                    if k < name:\n",
    "                        name_dic[k] += name_dic[name]\n",
    "                        name_dic[name] = -1\n",
    "                        name = k\n",
    "                    elif k > name:\n",
    "                        name_dic[name] += name_dic[k]\n",
    "                        name_dic[k] = -1\n",
    "                    else:\n",
    "                        pass\n",
    "        result = []\n",
    "        for k in name_dic:\n",
    "            if name_dic[k] >= 0:\n",
    "                s = k + '(' + str(name_dic[k]) + ')'\n",
    "                result.append(s)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        def find(pre_k, k, ks):\n",
    "            if not syn_dic[k]:\n",
    "                return\n",
    "            for w in syn_dic[k]:\n",
    "                if w and w not in ks and w not in syn_dic[pre_k]:\n",
    "                    ks.append(k)\n",
    "                    find(k, w, ks)\n",
    "                    ks.pop()\n",
    "                    if w in name_dic:\n",
    "                        syn_dic[pre_k].append(w)\n",
    "                    syn_dic[w] = None\n",
    "\n",
    "        name_dic = {}\n",
    "        for name in names:\n",
    "            w, n = name.split('(')\n",
    "            name_dic[w] = int(n[:-1])\n",
    "        syn_dic = {}\n",
    "        for s in synonyms:\n",
    "            s1, s2 = s.split(',')\n",
    "            name1 = s1[1:]\n",
    "            name2 = s2[:-1]\n",
    "            if name1 in name_dic or name2 in name_dic:\n",
    "                if name1 not in syn_dic:\n",
    "                    syn_dic[name1] = [name2]\n",
    "                else:\n",
    "                    syn_dic[name1].append(name2)\n",
    "                if name2 not in syn_dic:\n",
    "                    syn_dic[name2] = [name1]\n",
    "                else:\n",
    "                    syn_dic[name2].append(name1)\n",
    "        syn_dic[1] = []\n",
    "        for k in syn_dic:\n",
    "            syn_dic[1] = []\n",
    "            find(1, k, [])\n",
    "\n",
    "        res = []\n",
    "        for k in syn_dic:\n",
    "            if syn_dic[k]:\n",
    "                sub_res = [k] + syn_dic[k]\n",
    "                res.append(sub_res)\n",
    "        for n in res:\n",
    "            name = n[0]\n",
    "            for k in n:\n",
    "                if k in name_dic:\n",
    "                    if k < name:\n",
    "                        name_dic[k] += name_dic[name]\n",
    "                        name_dic[name] = -1\n",
    "                        name = k\n",
    "                    elif k > name:\n",
    "                        name_dic[name] += name_dic[k]\n",
    "                        name_dic[k] = -1\n",
    "                    else:\n",
    "                        pass\n",
    "        result = []\n",
    "        for k in name_dic:\n",
    "            if name_dic[k] >= 0:\n",
    "                s = k + '(' + str(name_dic[k]) + ')'\n",
    "                result.append(s)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        # 这道题不采用普通并查集class(数组)写是因为父亲数组需要动态变化\n",
    "        # hashmap可以灵活的增加元素\n",
    "        # 这道题容易忽视的corner case是names里面的两个name 通过中间的不曾出现过的name链接起来\n",
    "        # 譬如names里面a:14 d:13 连接关系(a,b)(b,c)(c,d)可以把ad合并\n",
    "        # 但是其他人的代码里都没体现这一点\n",
    "        f, cnt = {}, {}\n",
    "        for name in names:\n",
    "            n, c = name.split(\"(\")\n",
    "            f[n], cnt[n] = n, int(c[:-1])\n",
    "        \n",
    "        # 并查集查找同类根\n",
    "        def find(x):\n",
    "            if f[x] != x: \n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        for s in synonyms:\n",
    "            name1, name2 = s[1:-1].split(\",\")\n",
    "            # 不存在的话 仍然需要在f和cnt里进行增加 因为连接关系仍有用\n",
    "            if name1 not in f:\n",
    "                f[name1] = name1\n",
    "                cnt[name1] = 0\n",
    "            if name2 not in f:\n",
    "                f[name2] = name2\n",
    "                cnt[name2] = 0\n",
    "            p1, p2 = find(name1), find(name2)\n",
    "            if p1 == p2:\n",
    "                # 父亲一样 那么此时什么都不做\n",
    "                continue\n",
    "            # 父亲不一样 需要合并 字典序小的作为父亲\n",
    "            freq = cnt[p1] + cnt[p2]\n",
    "            fa = min(p1, p2)\n",
    "            ch = max(p1, p2)\n",
    "            f[ch] = fa\n",
    "            cnt[ch] = 0\n",
    "            cnt[fa] = freq\n",
    "\n",
    "        ans = {}\n",
    "        for k, v in f.items():\n",
    "            if k == v and cnt[k] != 0:\n",
    "                ans[k] = cnt[k]\n",
    "        return [k + '(' + str(v) + ')' for k, v in ans.items()]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        # 预处理\n",
    "        f, cnt = {}, {}\n",
    "        for name in names:\n",
    "            n, c = name.split(\"(\")\n",
    "            f[n], cnt[n] = n, int(c[:-1])\n",
    "        \n",
    "        # 并查集查找同类根\n",
    "        def find(x):\n",
    "            if f[x] != x: f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym.split(\",\")\n",
    "            # 如果当前同类名不在公布名单中，则更新字典\n",
    "            if f.get(name1[1:]) is None or f.get(name2[:-1]) is None: \n",
    "                if f.get(name1[1:]) is None:\n",
    "                    f[name1[1:]] = name1[1:]\n",
    "                    cnt[name1[1:]]=0\n",
    "                if f.get(name2[:-1]) is None: \n",
    "                    f[name2[:-1]] = name2[:-1]\n",
    "                    cnt[name2[:-1]]=0\n",
    "            p1, p2 = find(name1[1:]), find(name2[:-1])\n",
    "            # 保证同类根的字典序最小\n",
    "            if p1 > p2: f[p1] = p2\n",
    "            else: f[p2] = p1\n",
    "        \n",
    "        # 统计总频率\n",
    "        ans = collections.defaultdict(int)\n",
    "        for k, v in f.items():\n",
    "            ans[find(v)] += cnt[k]\n",
    "        \n",
    "        return [k+'('+str(v)+')' for k, v in ans.items()]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "#         parent = dict()\n",
    "#         nameList = reduce(lambda x, y: x+y, map(lambda x: x[1:-1].split(','), synonyms))\n",
    "#         synonyms = list(map(lambda x: x[1:-1].split(','), synonyms))\n",
    "\n",
    "#         def find(x):\n",
    "#             print(x)\n",
    "#             if x != nameList[parent[x]]:\n",
    "#                 parent[x] = find(nameList[parent[x]])\n",
    "#             return parent[x]\n",
    "        \n",
    "#         def union(x, y):\n",
    "#             print(x, y)\n",
    "#             xx = find(x)\n",
    "#             yy = find(y)\n",
    "#             print(xx, yy)\n",
    "\n",
    "#             parent[nameList[yy]] = xx\n",
    "\n",
    "#         for i, x in enumerate(nameList):\n",
    "#             if x not in parent:\n",
    "#                 parent[x] = i\n",
    "        \n",
    "#         for (x, y) in synonyms:\n",
    "#             union(x, y)\n",
    "        \n",
    "#         print(parent)\n",
    "#         nameDict = dict()\n",
    "#         counter = collections.Counter()\n",
    "#         for x in names:\n",
    "#             name, cnt = x.split('(')\n",
    "#             cnt = int(cnt[:-1])\n",
    "\n",
    "#             counter[]\n",
    "#         for k, v in parent.items():\n",
    "# from collections import defaultdict\n",
    "\n",
    "# class UnionFind(object):\n",
    "#     def __init__(self, names):\n",
    "#         self.parent = {}\n",
    "#         for name in names:\n",
    "#             self.parent[name] = name\n",
    "\n",
    "#     def union(self, a, b):\n",
    "#         if a not in self.parent or b not in self.parent:\n",
    "#             return\n",
    "#         root_a = self.find_root(a)\n",
    "#         root_b = self.find_root(b)\n",
    "#         if root_a < root_b:\n",
    "#             self.parent[root_b] = root_a\n",
    "#         else:\n",
    "#             self.parent[root_a] = root_b\n",
    "\n",
    "#     def find_root(self, node):\n",
    "#         if node != self.parent[node]:\n",
    "#             self.parent[node] = self.find_root(self.parent[node])\n",
    "#         return self.parent[node]\n",
    "        \n",
    "#         # while node != self.parent[node]:\n",
    "#         #     print(node, self.parent[node])\n",
    "#         #     self.parent[node] = self.parent[self.parent[node]]\n",
    "#         #     node = self.parent[node]\n",
    "#         # return node\n",
    "\n",
    "# class Solution(object):\n",
    "#     def trulyMostPopular(self, names, synonyms):\n",
    "#         \"\"\"\n",
    "#         leetcode17.07\n",
    "#         :type names: List[str]\n",
    "#         :type synonyms: List[str]\n",
    "#         :rtype: List[str]\n",
    "#         \"\"\"\n",
    "#         # 频率map\n",
    "#         freq_map = defaultdict(int)\n",
    "#         for name_freq in names:\n",
    "#             name, freq_str = (part.strip().strip(')') for part in name_freq.split('('))\n",
    "#             freq_map[name] = int(freq_str)\n",
    "#         # 初始化并查集\n",
    "#         uf = UnionFind(freq_map.keys())\n",
    "#         # 并操作\n",
    "#         for pair_str in synonyms:\n",
    "#             a, b = (name.strip().strip(')').strip('(') for name in pair_str.split(','))\n",
    "#             uf.union(a, b)\n",
    "#         print(uf.parent)\n",
    "\n",
    "#         # 生成结果\n",
    "#         result = []\n",
    "#         res_map = defaultdict(int)\n",
    "#         for name, freq in freq_map.items():\n",
    "#             res_map[uf.find_root(name)] += freq\n",
    "#         for name, freq in res_map.items():\n",
    "#             result.append('{}({})'.format(name, freq))\n",
    "#         return result\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        # 这道题不采用普通并查集class(数组)写是因为父亲数组需要动态变化\n",
    "        # hashmap可以灵活的增加元素\n",
    "        # 这道题容易忽视的corner case是names里面的两个name 通过中间的不曾出现过的name链接起来\n",
    "        # 譬如names里面a:14 d:13 连接关系(a,b)(b,c)(c,d)可以把ad合并\n",
    "        # 但是其他人的代码里都没体现这一点\n",
    "        f, cnt = {}, {}\n",
    "        for name in names:\n",
    "            n, c = name.split(\"(\")\n",
    "            f[n], cnt[n] = n, int(c[:-1])\n",
    "        \n",
    "        # 并查集查找同类根\n",
    "        def find(x):\n",
    "            if f[x] != x: \n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        for s in synonyms:\n",
    "            name1, name2 = s[1:-1].split(\",\")\n",
    "            # 不存在的话 仍然需要在f和cnt里进行增加 因为连接关系仍有用\n",
    "            if name1 not in f:\n",
    "                f[name1] = name1\n",
    "                cnt[name1] = 0\n",
    "            if name2 not in f:\n",
    "                f[name2] = name2\n",
    "                cnt[name2] = 0\n",
    "            p1, p2 = find(name1), find(name2)\n",
    "            if p1 == p2:\n",
    "                # 父亲一样 那么此时什么都不做\n",
    "                continue\n",
    "            # 父亲不一样 需要合并 字典序小的作为父亲\n",
    "            freq = cnt[p1] + cnt[p2]\n",
    "            fa = min(p1, p2)\n",
    "            ch = max(p1, p2)\n",
    "            f[ch] = fa\n",
    "            cnt[ch] = 0\n",
    "            cnt[fa] = freq\n",
    "        print(f)\n",
    "        ans = {}\n",
    "        for k, v in f.items():\n",
    "            if k == v and cnt[k] != 0:\n",
    "                ans[k] = cnt[k]\n",
    "        return [k + '(' + str(v) + ')' for k, v in ans.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        f = {}\n",
    "        names.sort()\n",
    "\n",
    "        def find(x):\n",
    "            f.setdefault(x, x)\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            a = find(x)\n",
    "            b = find(y)\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            if a != b:\n",
    "                f[b] = a\n",
    "        ab=[]\n",
    "        for s in synonyms:\n",
    "            li = s.split(',')\n",
    "            x, y = li[0][1:], li[1][:-1]\n",
    "            if x in ('Ghc','Aeax','Tlv','Qxkjt','Qweye') or y in ('Aeax','Ghc','Tlv','Qxkjt','Qweye'):\n",
    "                ab.append((x,y))\n",
    "            union(x, y)\n",
    "        sizes = collections.defaultdict(int)\n",
    "        for s in names:\n",
    "            i = s.index('(')\n",
    "            num = int(s[i + 1:-1])\n",
    "            sizes[find(s[:i])] += num\n",
    "        res = []\n",
    "        for name in sizes:\n",
    "            a = name + '(' + str(sizes[name]) + ')'\n",
    "            res.append(a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        d = {}\n",
    "        for name in names:\n",
    "            item = name[:-1].split('(')\n",
    "            d[item[0]] = (item[0], int(item[1]))\n",
    "        # print(d)\n",
    "        def find(n):\n",
    "            if d[n][0] == n:\n",
    "                return n\n",
    "            else:\n",
    "                return find(d[n][0])\n",
    "        def join(m, n):\n",
    "            # print((m, n))\n",
    "            if m not in d.keys():\n",
    "                d[m] = (m, 0)\n",
    "            if n not in d.keys():\n",
    "                d[n] = (n ,0)\n",
    "            name1 = find(m)\n",
    "            name2 = find(n)\n",
    "            if name1 != name2:\n",
    "                root = min(name1, name2)\n",
    "                root2 = max(name1, name2)\n",
    "                d[root] = (root, d[name1][1] + d[name2][1])\n",
    "                d[root2] = (root, d[root2][1])\n",
    "        for s in synonyms:\n",
    "            pairs = s[1:-1].split(',')\n",
    "            join(pairs[0],pairs[1])\n",
    "        ans = []\n",
    "        for k in d.keys():\n",
    "            if k == d[k][0]:\n",
    "                ans.append('{}({})'.format(d[k][0], d[k][1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        g = {}\n",
    "        def find(x):\n",
    "            if not x in g:\n",
    "                g[x] = [x, 0]\n",
    "            if g[x][0] == x:\n",
    "                return x\n",
    "            g[x][0] = find(g[x][0])\n",
    "            return g[x][0]\n",
    "        for x in names:\n",
    "            a, _, b = x.partition('(')\n",
    "            g[a] = [a, int(b[:-1])]\n",
    "        for x in synonyms:\n",
    "            a, _, b = x.partition(',')\n",
    "            a1, b1 = find(a[1:]), find(b[:-1])\n",
    "            g[max(a1, b1)][0] = min(a1, b1)\n",
    "        d = defaultdict(int)\n",
    "        for x in g:\n",
    "            d[find(x)] += g[x][1]\n",
    "        return [f'{x}({d[x]})' for x in d]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        g = {}\n",
    "        def find(x):\n",
    "            if not x in g:\n",
    "                g[x] = [x, 0]\n",
    "            if g[x][0] == x:\n",
    "                return x\n",
    "            g[x][0] = find(g[x][0])\n",
    "            return g[x][0]\n",
    "        for x in names:\n",
    "            a, _, b = x.partition('(')\n",
    "            g[a] = [a, int(b[:-1])]\n",
    "        for x in synonyms:\n",
    "            a, _, b = x.partition(',')\n",
    "            a1, b1 = find(a[1:]), find(b[:-1])\n",
    "            if a1 != b1:\n",
    "                g[max(a1, b1)][0] = min(a1, b1)\n",
    "        d = defaultdict(int)\n",
    "        for x in g:\n",
    "            d[find(x)] += g[x][1]\n",
    "        return [f'{x}({d[x]})' for x in d]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        # 预处理\n",
    "        f, cnt = {}, {}\n",
    "        for name in names:\n",
    "            n, c = name.split(\"(\")\n",
    "            f[n], cnt[n] = n, int(c[:-1])\n",
    "        \n",
    "        # 并查集查找同类根\n",
    "        def find(x):\n",
    "            if f[x] != x: f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym.split(\",\")\n",
    "            # 如果当前同类名不在公布名单中，则更新字典\n",
    "            if f.get(name1[1:]) is None or f.get(name2[:-1]) is None: \n",
    "                if f.get(name1[1:]) is None:\n",
    "                    f[name1[1:]] = name1[1:]\n",
    "                    cnt[name1[1:]]=0\n",
    "                if f.get(name2[:-1]) is None: \n",
    "                    f[name2[:-1]] = name2[:-1]\n",
    "                    cnt[name2[:-1]]=0\n",
    "            p1, p2 = find(name1[1:]), find(name2[:-1])\n",
    "            # 保证同类根的字典序最小\n",
    "            if p1 > p2: f[p1] = p2\n",
    "            else: f[p2] = p1\n",
    "        \n",
    "        # 统计总频率\n",
    "        ans = collections.defaultdict(int)\n",
    "        for k, v in f.items():\n",
    "            ans[find(v)] += cnt[k]\n",
    "        \n",
    "        return [k+'('+str(v)+')' for k, v in ans.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        def find(x):\n",
    "            if x not in group:\n",
    "                group[x] = x\n",
    "                return x\n",
    "            if group[x] != x:\n",
    "                group[x] = find(group[x])\n",
    "            return group[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            gx = find(x)\n",
    "            gy = find(y)\n",
    "            if gx > gy:\n",
    "                group[gx] = gy \n",
    "            else:\n",
    "                group[gy] = gx\n",
    "\n",
    "        group = {}\n",
    "        count = {} \n",
    "        for item in names:\n",
    "            name, num = item[:-1].split('(')\n",
    "            group[name] = name\n",
    "            count[name] = int(num)\n",
    "        for pair in synonyms:\n",
    "            name1, name2 = pair[1:-1].split(',')\n",
    "            union(name1, name2)\n",
    "\n",
    "        res = defaultdict(int)\n",
    "        for name, num in count.items():\n",
    "            res[find(name)] += num\n",
    "        return [f'{name}({num})' for name, num in res.items()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        \n",
    "\n",
    "        f,cnt = {},{}\n",
    "        for name in names:\n",
    "            n,c = name.split('(')\n",
    "            f[n],cnt[n] = n,int(c[:-1])\n",
    "        \n",
    "        def find(x):\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        for syn in synonyms:\n",
    "            name1,name2 = syn[1:-1].split(',')\n",
    "            if name1 not in f:\n",
    "                f[name1] = name1\n",
    "                cnt[name1] = 0\n",
    "            if name2 not in f:\n",
    "                f[name2] = name2\n",
    "                cnt[name2] = 0\n",
    "            p1,p2 = find(name1),find(name2)\n",
    "            if p1 == p2:\n",
    "                continue\n",
    "            freq = cnt[p1] + cnt[p2]\n",
    "            fa = min(p1,p2)\n",
    "            ch = max(p1,p2)\n",
    "            f[ch] = fa\n",
    "            cnt[fa] = freq\n",
    "            cnt[ch] = 0\n",
    "        ans = {}\n",
    "        for k,v in f.items():\n",
    "            if k == v and cnt[k] != 0:\n",
    "                ans[k] = cnt[k]\n",
    "        return [k + '(' + str(ans[k]) + ')' for k,v in ans.items()]\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def trulyMostPopular(self, names, synonyms):\n",
    "        # 预处理\n",
    "        f, cnt = {}, {}\n",
    "        for name in names:\n",
    "            n, c = name.split(\"(\")\n",
    "            f[n], cnt[n] = n, int(c[:-1])\n",
    "        \n",
    "        # 并查集查找同类根\n",
    "        def find(x):\n",
    "            if f[x] != x: f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym.split(\",\")\n",
    "            # 如果当前同类名不在公布名单中，则更新字典\n",
    "            if f.get(name1[1:]) is None or f.get(name2[:-1]) is None: \n",
    "                if f.get(name1[1:]) is None:\n",
    "                    f[name1[1:]] = name1[1:]\n",
    "                    cnt[name1[1:]]=0\n",
    "                if f.get(name2[:-1]) is None: \n",
    "                    f[name2[:-1]] = name2[:-1]\n",
    "                    cnt[name2[:-1]]=0\n",
    "            p1, p2 = find(name1[1:]), find(name2[:-1])\n",
    "            # 保证同类根的字典序最小\n",
    "            if p1 > p2: f[p1] = p2\n",
    "            else: f[p2] = p1\n",
    "        \n",
    "        # 统计总频率\n",
    "        ans = collections.defaultdict(int)\n",
    "        for k, v in f.items():\n",
    "            ans[find(v)] += cnt[k]\n",
    "        \n",
    "        return [k+'('+str(v)+')' for k, v in ans.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        sz = {}\n",
    "        rnames = set()\n",
    "        for name in names:\n",
    "            na, d = name.split('(')\n",
    "            rnames.add(na)\n",
    "            sz[na] = int(d[:-1])\n",
    "        roots = {na:na for na in sz}\n",
    "        def find(x):\n",
    "            if roots[x] != x:\n",
    "                roots[x] = find(roots[x])\n",
    "            return roots[x]\n",
    "        def union(x, y):\n",
    "            if x not in roots:\n",
    "                roots[x] = x\n",
    "                sz[x] = 0\n",
    "            if y not in roots:\n",
    "                roots[y] = y\n",
    "                sz[y] = 0\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                if rx < ry:\n",
    "                    roots[ry] = rx\n",
    "                    sz[rx] += sz[ry]\n",
    "                else:\n",
    "                    roots[rx] = ry\n",
    "                    sz[ry] += sz[rx]\n",
    "        for sy in synonyms:\n",
    "            x, y = sy.split(',')\n",
    "            x, y = x[1:], y[:-1]\n",
    "            union(x, y)\n",
    "        chils = defaultdict(int)\n",
    "        for na in rnames:\n",
    "            chils[find(na)] = sz[find(na)]\n",
    "        return [f'{na}({d})' for na, d in chils.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        def union(x, y):\n",
    "            px, py = find(x), find(y)\n",
    "            if px < py:\n",
    "                table[py] = px\n",
    "            else:\n",
    "                table[px] = py\n",
    "\n",
    "        def find(x):\n",
    "            if x not in table:\n",
    "                table[x] = x\n",
    "                return x\n",
    "            if table[x] != x:\n",
    "                table[x] = find(table[x])\n",
    "            return table[x]\n",
    "\n",
    "        table = {}\n",
    "        for synonym in synonyms:\n",
    "            items = synonym.split(',')\n",
    "            name1, name2 = items[0][1:], items[1][:-1]\n",
    "            union(name1, name2)\n",
    "        freqs = {}\n",
    "        for item in names:\n",
    "            items = item.split('(')\n",
    "            name = items[0]\n",
    "            freq = int(items[1][:-1])\n",
    "            freqs[find(name)] = freqs.get(find(name), 0) +  freq\n",
    "        res = []\n",
    "        for name in freqs:\n",
    "            res.append(name + '(' + str(freqs[name]) + ')')\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        nums,words = {},{}\n",
    "        for c in names:\n",
    "            s,c = c.split('(')\n",
    "            nums[s]=int(c[:-1])\n",
    "            words[s] = s\n",
    "\n",
    "        def find(x):\n",
    "            if words[x]!=x:words[x] = find(words[x])\n",
    "            return words[x]\n",
    "\n",
    "        \n",
    "        for c in synonyms:\n",
    "            m = c.split(',')\n",
    "            m0,m1 = m[0][1:],m[1][:-1]\n",
    "            if words.get(m0) is None:\n",
    "                words[m0]=m0\n",
    "                nums[m0] = 0\n",
    "            if words.get(m1) is None:\n",
    "                words[m1]=m1\n",
    "                nums[m1] = 0\n",
    "            p1,p2 = find(m0),find(m1)\n",
    "            if p1>p2:\n",
    "                words[p1] = p2\n",
    "            else:\n",
    "                words[p2] = p1\n",
    "        res = collections.defaultdict(int)\n",
    "        for k,v in words.items():\n",
    "            res[find(v)] += nums[k]\n",
    "        return [k+'('+str(v)+')' for k,v in res.items()]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        nums,words = {},{}\n",
    "        for c in names:\n",
    "            s,c = c.split('(')\n",
    "            nums[s]=int(c[:-1])\n",
    "            words[s] = s\n",
    "\n",
    "        def find(x):\n",
    "            if words[x]!=x:words[x] = find(words[x])\n",
    "            return words[x]\n",
    "\n",
    "        \n",
    "        for c in synonyms:\n",
    "            m = c.split(',')\n",
    "            m0,m1 = m[0][1:],m[1][:-1]\n",
    "            if words.get(m0) is None:\n",
    "                words[m0]=m0\n",
    "                nums[m0] = 0\n",
    "            if words.get(m1) is None:\n",
    "                words[m1]=m1\n",
    "                nums[m1] = 0\n",
    "            p1,p2 = find(m0),find(m1)\n",
    "            if p1>p2:\n",
    "                words[p1] = p2\n",
    "            else:\n",
    "                words[p2] = p1\n",
    "        res = collections.defaultdict(int)\n",
    "        for k,v in words.items():\n",
    "            res[find(v)] += nums[k]\n",
    "        return [k+'('+str(v)+')' for k,v in res.items()]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        nums,words = {},{}\n",
    "        for c in names:\n",
    "            s,c = re.match('[a-zA-Z]+',c).group(0),re.search('\\d+',c).group()\n",
    "            nums[s]=int(c)\n",
    "            words[s] = s\n",
    "\n",
    "        def find(x):\n",
    "            if words[x]!=x:words[x] = find(words[x])\n",
    "            return words[x]\n",
    "\n",
    "        \n",
    "        for c in synonyms:\n",
    "            m = match('\\(([a-zA-Z]+),([a-zA-Z]+)\\)',c).groups()\n",
    "            if words.get(m[0]) is None:\n",
    "                words[m[0]]=m[0]\n",
    "                nums[m[0]] = 0\n",
    "            if words.get(m[1]) is None:\n",
    "                words[m[1]]=m[1]\n",
    "                nums[m[1]] = 0\n",
    "            # print(words)\n",
    "            p1,p2 = find(m[0]),find(m[1])\n",
    "            if p1>p2:\n",
    "                words[p1] = p2\n",
    "            else:\n",
    "                words[p2] = p1\n",
    "        res = collections.defaultdict(int)\n",
    "        for k,v in words.items():\n",
    "            res[find(v)] += nums[k]\n",
    "        return [k+'('+str(v)+')' for k,v in res.items()]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        nums,words = {},{}\n",
    "        for c in names:\n",
    "            s,c = re.match('[a-zA-Z]+',c).group(0),re.search('\\d+',c).group()\n",
    "            nums[s]=int(c)\n",
    "            words[s] = s\n",
    "\n",
    "        def find(x):\n",
    "            if words[x]!=x:words[x] = find(words[x])\n",
    "            return words[x]\n",
    "\n",
    "        \n",
    "        for c in synonyms:\n",
    "            m = match('\\(([a-zA-Z]+),([a-zA-Z]+)\\)',c).groups()\n",
    "            if words.get(m[0]) is None:\n",
    "                words[m[0]]=m[0]\n",
    "                nums[m[0]] = 0\n",
    "            if words.get(m[1]) is None:\n",
    "                words[m[1]]=m[1]\n",
    "                nums[m[1]] = 0\n",
    "            # print(words)\n",
    "            p1,p2 = find(m[0]),find(m[1])\n",
    "            if p1>p2:\n",
    "                words[p1] = p2\n",
    "            else:\n",
    "                words[p2] = p1\n",
    "        res = collections.defaultdict(int)\n",
    "        for k,v in words.items():\n",
    "            res[find(v)] += nums[k]\n",
    "        return [k+'('+str(v)+')' for k,v in res.items()]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        uf = {}\n",
    "        def find(x): uf[x] = x if uf.get(x, x) == x else find(uf[x]); return uf[x]\n",
    "        def join(x, y): x, y = max(find(x), find(y)), min(find(x), find(y)); uf[x] = y\n",
    "        d, keys = {}, []\n",
    "        for s in names:\n",
    "            i = s.find('(')\n",
    "            d[s[:i]] = int(s[i + 1:-1])\n",
    "            keys.append(s[:i])\n",
    "        for s in synonyms:\n",
    "            x, y = s.strip('()').split(',')\n",
    "            join(x, y)\n",
    "        a = {}\n",
    "        for k in keys:\n",
    "            a[find(k)] = a.get(find(k), 0) + d.get(k, 0)\n",
    "        return [f'{name}({a[name]})' for name in sorted(a.keys())]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        all_names = set(map(lambda x:x.split('(')[0], names))\n",
    "        for syn in synonyms:\n",
    "            a,b = syn[1:-1].split(',')\n",
    "            all_names.add(a)\n",
    "            all_names.add(b)\n",
    "\n",
    "        parents = {n:n for n in all_names}\n",
    "        rank = {n:0 for n in all_names}\n",
    "\n",
    "        def find(a):\n",
    "            if parents[a] != a:\n",
    "                parents[a] = find(parents[a])\n",
    "            return parents[a]\n",
    "\n",
    "        def union(a, b):\n",
    "            para = find(a)\n",
    "            parb = find(b)\n",
    "            if para != parb:\n",
    "                if rank[para] < rank[parb]:\n",
    "                    para, parb = parb, para\n",
    "                parents[parb] = para\n",
    "                if rank[para] == rank[parb]:\n",
    "                    rank[para] += 1\n",
    "        \n",
    "        for syn in synonyms:\n",
    "            a,b = syn[1:-1].split(',')\n",
    "            union(a,b)\n",
    "        \n",
    "        cnts = {}\n",
    "        minname = {}\n",
    "\n",
    "        for name in names:\n",
    "            n, num = name.split('(')\n",
    "            num = int(num[:-1])\n",
    "            par = find(n)\n",
    "            if par not in cnts:\n",
    "                cnts[par] = 0\n",
    "                minname[par] = par\n",
    "            \n",
    "            cnts[par] += num\n",
    "            minname[par] = min(minname[par], n)\n",
    "        \n",
    "        for name in all_names:\n",
    "            par = find(name)\n",
    "            minname[par] = min(minname[par], name)\n",
    "        \n",
    "        res = []\n",
    "        for name in minname:\n",
    "            res.append(minname[name]+\"(\"+str(cnts[name])+\")\")\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def trulyMostPopular(self, names, synonyms):\n",
    "        l = {}\n",
    "        f = {}\n",
    "        for i in names:\n",
    "            p,q = i.split('(')\n",
    "            q = q.replace(\")\",'')\n",
    "            l[p] = q\n",
    "            f[p] = p\n",
    "        \n",
    "        def find(x):\n",
    "            if f[x] != x: x = find(f[x])\n",
    "            return x\n",
    "\n",
    "        for i in synonyms:\n",
    "            m,n = i.replace('(',\"\").replace(\")\",\"\").split(',')\n",
    "            if m not in f or n not in f: \n",
    "                if m not in f:\n",
    "                    f[m] = m\n",
    "                else:\n",
    "                    f[n] = n\n",
    "            p,q = find(m),find(n)\n",
    "            if p > q: f[p] = q\n",
    "            else: f[q] = p\n",
    "\n",
    "        g = {}\n",
    "        for i in l:\n",
    "            x = find(i)\n",
    "            if x not in g:\n",
    "                g[x] = int(l[i])\n",
    "            else:\n",
    "                g[x] += int(l[i])\n",
    "        z = []\n",
    "        for x,y in g.items():\n",
    "            z.append(x+\"(\"+str(y)+\")\")\n",
    "\n",
    "        return z\n",
    "#  class Solution(object):\n",
    "#     def trulyMostPopular(self, names, synonyms):\n",
    "#         # 预处理\n",
    "#         f, cnt = {}, {}\n",
    "#         for name in names:\n",
    "#             n, c = name.split(\"(\")\n",
    "#             f[n], cnt[n] = n, int(c[:-1])\n",
    "        \n",
    "#         # 并查集查找同类根\n",
    "#         def find(x):\n",
    "#             if f[x] <> x: f[x] = find(f[x])\n",
    "#             return f[x]\n",
    "\n",
    "#         for synonym in synonyms:\n",
    "#             name1, name2 = synonym.split(\",\")\n",
    "#             # 如果当前同类名不在公布名单中，则跳过\n",
    "#             if f.get(name1[1:]) is None or f.get(name2[:-1]) is None: continue\n",
    "#             p1, p2 = find(name1[1:]), find(name2[:-1])\n",
    "#             # 保证同类根的字典序最小\n",
    "#             if p1 > p2: f[p1] = p2\n",
    "#             else: f[p2] = p1\n",
    "        \n",
    "#         # 统计总频率\n",
    "#         ans = collections.defaultdict(int)\n",
    "#         for k, v in f.iteritems():\n",
    "#             ans[find(v)] += cnt[k]\n",
    "        \n",
    "#         return [k+'('+str(v)+')' for k, v in ans.iteritems()]\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        # 是否属于一个集合 类似是否为亲戚关系 使用并查集\n",
    "        # 1. 初始化并查集数组\n",
    "        ori_dict = {}\n",
    "        parent = {}\n",
    "        for x in names:\n",
    "            name = x.split('(')[0]\n",
    "            num = x.split('(')[1].split(')')[0]\n",
    "            ori_dict[name] = int(num)\n",
    "            parent[name] = name\n",
    "        \n",
    "        # 2. 合并关系\n",
    "        def find(node):\n",
    "            if node == parent[node]:\n",
    "                return node\n",
    "            else:\n",
    "                parent[node] = find(parent[node]) # 路径压缩\n",
    "                return parent[node]\n",
    "        \n",
    "        def union(a,b):\n",
    "            if a not in parent:\n",
    "                parent[a] = a\n",
    "            if b not in parent:\n",
    "                parent[b] = b\n",
    "            \n",
    "            a_parent = find(a)\n",
    "            b_parent = find(b)\n",
    "            if a_parent < b_parent:\n",
    "                parent[b_parent] = a_parent # 需要把b的祖先连到a的祖先下面; 否则b的祖先就不会和a的祖先化成一家人\n",
    "            else:\n",
    "                parent[a_parent] = b_parent\n",
    "        \n",
    "        for x in synonyms:\n",
    "            a,b = x.split('(')[1].split(')')[0].split(',')\n",
    "            union(a,b)\n",
    "        \n",
    "        res = []\n",
    "        parent_fre_dict = {}\n",
    "        for name,num in ori_dict.items():\n",
    "            parent_name = find(name)\n",
    "            if parent_name not in parent_fre_dict:\n",
    "                parent_fre_dict[parent_name] = num\n",
    "            else:\n",
    "                parent_fre_dict[parent_name] += num\n",
    "\n",
    "        for name,num in parent_fre_dict.items():\n",
    "            res.append(name+\"(\"+str(num)+\")\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str],\n",
    "                         synonyms: List[str]) -> List[str]:\n",
    "        # 并查集, 先找到所有相同的名字, 然后再统计数字\n",
    "        # 注意祖先需要是字典序最小的, 所以需要稍微改动union逻辑\n",
    "        pre = {}\n",
    "\n",
    "        def find(x):\n",
    "            if x not in pre:\n",
    "                pre[x] = x\n",
    "            elif pre[x] != x:\n",
    "                pre[x] = find(pre[x])\n",
    "            return pre[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            px = find(x)\n",
    "            py = find(y)\n",
    "            mn, mx = min(px, py), max(px, py)\n",
    "            pre[mx] = mn\n",
    "\n",
    "        for s in synonyms:\n",
    "            x, y = s[1:-1].split(',')\n",
    "            union(x, y)\n",
    "        cnts = defaultdict(int)\n",
    "        for t in names:\n",
    "            i = t.find('(')\n",
    "            name = t[:i]\n",
    "            cnt = int(t[i + 1:t.find(')')])\n",
    "            cnts[find(name)] += cnt\n",
    "        res = []\n",
    "        for k in cnts:\n",
    "            res.append(k + '(' + str(cnts[k]) + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str],\n",
    "                         synonyms: List[str]) -> List[str]:\n",
    "        # 并查集变种, 先找到所有相同的名字, 然后再统计数字\n",
    "        # 注意祖先需要是字典序最小的, 所以需要稍微改动union逻辑\n",
    "        pre = {}\n",
    "\n",
    "        def find(x):\n",
    "            if x not in pre:\n",
    "                pre[x] = x\n",
    "            elif pre[x] != x:\n",
    "                pre[x] = find(pre[x])\n",
    "            return pre[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            px = find(x)\n",
    "            py = find(y)\n",
    "            # 保证祖先的字典序更小\n",
    "            if px > py:\n",
    "                pre[px] = py\n",
    "            else:\n",
    "                pre[py] = px\n",
    "\n",
    "        for s in synonyms:\n",
    "            # parse两个名字, 并合并\n",
    "            x, y = s[1:-1].split(',')\n",
    "            union(x, y)\n",
    "        cnts = defaultdict(int)\n",
    "        for t in names:\n",
    "            i = t.find('(')\n",
    "            # parse当前名字和频率\n",
    "            name = t[:i]\n",
    "            cnt = int(t[i + 1:t.find(')')])\n",
    "            # 累加到祖先对应的频率中\n",
    "            cnts[find(name)] += cnt\n",
    "        res = []\n",
    "        for k in cnts:\n",
    "            # 转换成结果要求的格式\n",
    "            res.append(k + '(' + str(cnts[k]) + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names, synonyms):\n",
    "        def find(name):\n",
    "            if name not in hash_map.keys():\n",
    "                hash_map[name] = name\n",
    "                return name\n",
    "            if hash_map[name] == name:\n",
    "                return name\n",
    "            return find(hash_map[name])  # 递归查找根节点\n",
    "\n",
    "        def union(name1, name2):\n",
    "            root1 = find(name1)\n",
    "            root2 = find(name2)\n",
    "            if root1 != root2:\n",
    "                # 将两个集合合并，将其中一个集合的根节点指向另一个集合的根节点\n",
    "                if root1 < root2:\n",
    "                    hash_map[root2] = root1\n",
    "                else:\n",
    "                    hash_map[root1] = root2\n",
    "\n",
    "        name_nums = {}\n",
    "        hash_map = {}\n",
    "\n",
    "        # 初始化哈希表和名字数量字典\n",
    "        for item in names:\n",
    "            name, num = item.split('(')\n",
    "            num = int(num[:-1])\n",
    "            name_nums[name] = num\n",
    "            hash_map[name] = name\n",
    "\n",
    "        # 处理同义词，进行合并操作\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym[1:-1].split(',')\n",
    "            union(name1, name2)\n",
    "\n",
    "        # 统计同一集合中的名字数量总和\n",
    "        result = defaultdict(int)\n",
    "        for name, num in name_nums.items():\n",
    "            root = find(name)\n",
    "            result[root] += num\n",
    "\n",
    "        # 将结果转换为要求的格式\n",
    "        output = []\n",
    "        for root, total_num in result.items():\n",
    "            output.append(f\"{root}({total_num})\")\n",
    "\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        # 预处理\n",
    "        f, cnt = {}, {}\n",
    "        for name in names:\n",
    "            n, c = name.split(\"(\")\n",
    "            f[n], cnt[n] = n, int(c[:-1])\n",
    "        \n",
    "        # 并查集查找同类根\n",
    "        def find(x):\n",
    "            if x not in f: \n",
    "                f[x] = x\n",
    "                cnt[x] = 0\n",
    "            if f[x] != x: f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym.split(\",\")\n",
    "            # 如果当前同类名不在公布名单中，则跳过\n",
    "            # if not f.get(name1[1:]) or not f.get(name2[:-1]): continue\n",
    "            p1, p2 = find(name1[1:]), find(name2[:-1])\n",
    "            # 保证同类根的字典序最小\n",
    "            if p1 > p2: f[p1] = p2\n",
    "            else: f[p2] = p1\n",
    "        \n",
    "        # 统计总频率\n",
    "        ans = collections.defaultdict(int)\n",
    "        for k, v in f.items():\n",
    "            ans[find(v)] += cnt[k]\n",
    "        \n",
    "        return [k+'('+str(v)+')' for k, v in ans.items()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        father={}\n",
    "        frequency={}\n",
    "        def union(x,y) :\n",
    "            yAncestor = find(y)\n",
    "            xAncestor = find(x)\n",
    "            if xAncestor>yAncestor:\n",
    "                father[xAncestor]=yAncestor\n",
    "            else:\n",
    "                father[yAncestor]=xAncestor\n",
    "\n",
    "\n",
    "\n",
    "        def find(x):\n",
    "            if father[x]==x:\n",
    "                return x\n",
    "            else:\n",
    "                return find(father[x])\n",
    "\n",
    "        for i in names:\n",
    "            name = i[0:i.index('(')]\n",
    "            father[name] = name\n",
    "            frequency[i[0:i.index('(')]]=int(i[i.index('(')+1:len(i)-1])\n",
    "\n",
    "        # print(father)\n",
    "        print(frequency)\n",
    "        for i in synonyms:\n",
    "            name1, name2 = i[1:i.index(',')], i[i.index(',')+1:len(i)-1]\n",
    "            if name1 not in father:\n",
    "                father[name1] = name1\n",
    "            if name2 not in father:\n",
    "                father[name2] = name2\n",
    "            union(name1,name2)\n",
    "\n",
    "        retDict={}\n",
    "        for i in frequency:\n",
    "            root = find(i)\n",
    "            if root not in retDict:\n",
    "                retDict[root]=0;\n",
    "            retDict[root] = retDict[root] +frequency[i]\n",
    "\n",
    "        ret=[]\n",
    "        for i in retDict:\n",
    "            ret.append(i+'('+str(retDict[i])+')')\n",
    "\n",
    "        print(ret)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "#         def split_name(n):\n",
    "#             for i in range(len(n)):\n",
    "#                 if n[i] == \"(\":\n",
    "#                     name = n[:i]\n",
    "#                     times = int(n[i+1:-1])\n",
    "#             return name, times\n",
    "\n",
    "\n",
    "#         d = {}\n",
    "#         f = {}\n",
    "#         for name in names:\n",
    "#             n, c = split_name(name)\n",
    "#             f[n], d[n] = n, c\n",
    "#         for couple in synonyms:\n",
    "#             first, second = couple.split(\",\")\n",
    "#             first, second = first[1:], second[:-1]\n",
    "#             if first not in d and second not in d:\n",
    "#                 continue\n",
    "#             if first > second:\n",
    "#                 f[first] = second\n",
    "#             else:\n",
    "#                 f[second] = first\n",
    "#         ans = {}\n",
    "#         for k, v in f.items():\n",
    "#             ans[f[v]] = ans.get(f[v], 0) + d[k]\n",
    "\n",
    "#         return [k+\"(\"+str(v)+\")\" for k, v in ans.items()]\n",
    "\n",
    "class Solution(object):\n",
    "    def trulyMostPopular(self, names, synonyms):\n",
    "        # 预处理\n",
    "        f, cnt = {}, {}\n",
    "        for name in names:\n",
    "            n, c = name.split(\"(\")\n",
    "            f[n], cnt[n] = n, int(c[:-1])\n",
    "        \n",
    "        # 并查集查找同类根\n",
    "        def find(x):\n",
    "            if f[x] != x: f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        for synonym in synonyms:\n",
    "            name1, name2 = synonym.split(\",\")\n",
    "            # 如果当前同类名不在公布名单中，则跳过\n",
    "            if f.get(name1[1:]) is None or f.get(name2[:-1]) is None: continue\n",
    "            p1, p2 = find(name1[1:]), find(name2[:-1])\n",
    "            # 保证同类根的字典序最小\n",
    "            if p1 > p2: f[p1] = p2\n",
    "            else: f[p2] = p1\n",
    "        \n",
    "        # 统计总频率\n",
    "        ans = collections.defaultdict(int)\n",
    "        for k, v in f.items():\n",
    "            ans[find(v)] += cnt[k]\n",
    "        \n",
    "        return [k+'('+str(v)+')' for k, v in ans.items()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        nums = {}\n",
    "        for c in names:\n",
    "            nums[re.match('[a-zA-Z]+',c).group(0)]=int(re.search('\\d+',c).group())\n",
    "        words = collections.defaultdict(set)\n",
    "        for c in synonyms:\n",
    "            m = match('\\(([a-zA-Z]+),([a-zA-Z]+)\\)',c).groups()\n",
    "            words[m[0]].add(m[1])\n",
    "            words[m[1]].add(m[0])\n",
    "        visited,res = set(),[]\n",
    "        # print(words,'**********',nums)\n",
    "\n",
    "        def dfs(key,tmp):\n",
    "            if key in visited:return set([])\n",
    "            visited.add(key)\n",
    "            tmp |= words[key]\n",
    "            for c in words[key]:\n",
    "                if c in visited:continue\n",
    "                tmp |= words[c]\n",
    "                tmp |= dfs(c,tmp)\n",
    "                visited.add(c)\n",
    "            return tmp\n",
    "\n",
    "        for key in words:\n",
    "            if key in visited:continue\n",
    "            total,tmp = 0,set()\n",
    "            tmp |= dfs(key,tmp)\n",
    "            # print(tmp)\n",
    "            for c in tmp:\n",
    "                if c in nums:\n",
    "                    total += nums[c]\n",
    "            res.append(sorted(list(tmp))[0]+'('+str(total)+')')\n",
    "        for c in nums:\n",
    "            if c in visited:continue\n",
    "            res.append(c+'('+str(nums[c])+')')\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        nums = {}\n",
    "        for c in names:\n",
    "            nums[re.match('[a-zA-Z]+',c).group(0)]=int(re.search('\\d+',c).group())\n",
    "        words = collections.defaultdict(set)\n",
    "        for c in synonyms:\n",
    "            m = match('\\(([a-zA-Z]+),([a-zA-Z]+)\\)',c).groups()\n",
    "            words[m[0]].add(m[1])\n",
    "            words[m[1]].add(m[0])\n",
    "        visited,res = set(),[]\n",
    "\n",
    "        def dfs(key,tmp):\n",
    "            if key in visited:return set([])\n",
    "            visited.add(key)\n",
    "            tmp |= words[key]\n",
    "            for c in words[key]:\n",
    "                if c in visited:continue\n",
    "                tmp |= words[c]\n",
    "                tmp |= dfs(c,tmp)\n",
    "                visited.add(c)\n",
    "            return tmp\n",
    "\n",
    "        for key in words:\n",
    "            if key in visited:continue\n",
    "            total,tmp = 0,set()\n",
    "            tmp |= dfs(key,tmp)\n",
    "            for c in tmp:\n",
    "                if c in nums:\n",
    "                    total += nums[c]\n",
    "            res.append(sorted(list(tmp))[0]+'('+str(total)+')')\n",
    "        for c in nums:\n",
    "            if c in visited:continue\n",
    "            res.append(c+'('+str(nums[c])+')')\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:\n",
    "        nums = {}\n",
    "        for c in names:\n",
    "            s,c = c.split('(')\n",
    "            nums[s]=int(c[:-1])\n",
    "        words = collections.defaultdict(set)\n",
    "        for c in synonyms:\n",
    "            m = c.split(',')\n",
    "            m0,m1 = m[0][1:],m[1][:-1]\n",
    "            words[m0].add(m1)\n",
    "            words[m1].add(m0)\n",
    "        visited,res = set(),[]\n",
    "\n",
    "        def dfs(key,tmp):\n",
    "            if key in visited:return set([])\n",
    "            visited.add(key)\n",
    "            tmp |= words[key]\n",
    "            for c in words[key]:\n",
    "                if c in visited:continue\n",
    "                tmp |= words[c]\n",
    "                tmp |= dfs(c,tmp)\n",
    "                visited.add(c)\n",
    "            return tmp\n",
    "\n",
    "        for key in words:\n",
    "            if key in visited:continue\n",
    "            total,tmp = 0,set()\n",
    "            tmp |= dfs(key,tmp)\n",
    "            for c in tmp:\n",
    "                if c in nums:\n",
    "                    total += nums[c]\n",
    "            res.append(sorted(list(tmp))[0]+'('+str(total)+')')\n",
    "        for c in nums:\n",
    "            if c in visited:continue\n",
    "            res.append(c+'('+str(nums[c])+')')\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
